Electrical computers and digital processing systems: processing – Processing architecture – Microprocessor or multichip or multimodule processor having...
Reexamination Certificate
1998-02-18
2001-05-22
Follansbee, John A. (Department: 2783)
Electrical computers and digital processing systems: processing
Processing architecture
Microprocessor or multichip or multimodule processor having...
C711S153000
Reexamination Certificate
active
06237079
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to memory management techniques in co-processor systems.
BACKGROUND OF THE INVENTION
Modern computer systems typically require some method of memory management to provide for dynamic memory allocation. In the case of a system with one or more co-processors, some method is necessary to synchronize between the dynamic allocation of memory and the use of that memory by a co-processor.
In a typical hardware configuration of a CPU with a specialised co-processor, both share a bank of memory. In such a system, the CPU is the only entity in the system capable of allocating memory dynamically. Once allocated by the CPU for use by the co-processor, this memory can be used freely by the co-processor until it is no longer required, at which point it is able to be freed by the CPU. This implies that some form of synchronization is necessary between the CPU and the co-processor in order to ensure that the memory is released only after the co-processor is finished using it.
Several possible solutions to this problem have undesirable performance implications. Use of statically allocated memory would avoid the need for synchronization, but would prevent the system from adjusting its memory resource usage dynamically. Alternatively, having the CPU block and wait until the co-processor has finished performing each operation would substantially reduce parallelism and hence reduce the overall system performance. Similarly, the use of interrupts to indicate completion of operations by the co-processor would also impose significant processing overhead if co-processor throughput is very high. So these prior art solutions are not attractive.
In addition to the need for high performance, such a system also has to deal with dynamic memory shortages gracefully. Most computer systems allow a wide range of memory size configurations. It is important that a system with large amounts of memory available to it make full use of the available resources to maximise performance. However, systems with minimal configurations must still perform adequately to be usable and at the very least degrade gracefully in the face of a memory shortage.
To overcome these problems, a synchronization mechanism is desired which will maximise system performance while also allowing co-processor memory usage to adjust dynamically to both the capacity of the system, and the complexity of the operation being performed. The present invention is based upon the realisation that after co-processor instructions have been completed, they can be placed in a “clean-up” queue and from time to time the memory resources allocated to these executed instructions can be reallocated by the CPU.
SUMMARY OF THE INVENTION
In accordance with one aspect of the present invention, there is disclosed a method of controlling the interaction between a host CPU and at least one co-processor in a computer system to permit substantially simultaneous decoupled execution of CPU instructions and co-processor instructions, and dynamic allocation of commonly used memory space during the course of the execution of said instructions, said method comprising the steps of:
(a) said host CPU allocating memory resources to be utilized by a set of instructions to be co-processor executed;
(b) generating a queue of pending co-processor instructions to be executed and a clean up queue of co-processor instructions for which execution has been completed;
(c) from time to time, under control of said host CPU, releasing for reallocation memory resources previously utilized by the instructions contained in said clean up queue of executed instructions.
Preferably the release of the allocated memory is carried out after the execution of a specific instruction. This instruction can be the last instruction in a pending instruction queue or it can be a predetermined instruction which utilises very substantial memory resources. Alternatively, the host CPU can detect that currently free memory resources are low (or exhausted) and thereby initiate the release of allocated memory which is no longer in use by the coprocessor.
In accordance with a second aspect of the present invention there is disclosed dynamic memory management means in a computer system having a memory of predetermined size, a host CPU and at least one co-processor, said memory management means comprising:
(a) an instruction generator means connected with said host CPU and generating a sequence of instructions intended for co-processor execution,
(b) a memory manager means connected to said memory and said instruction generator means to dynamically allocate space in said memory for co-processor use in executing said sequence of co-processor instructions,
(c) a queue manager means connected to said instruction generator means, said memory manager means and said co-processor, said queue manager means being arranged to store said sequence of instructions in a queue of pending instructions to be co-processor executed and a clean up queue of instructions which have been co-processor executed,
wherein from time to time said queue manager means removes executed instructions from said clean up queue to thereby release for reallocation memory space previously allocated to said removed executed instructions.
Various ways of triggering the operation of the queue manger means are preferably provided including the memory manger means being unable to satisfy a request for memory space or interrupting the CPU processing until a predetermined fraction (eg ⅓ or ½) of the queue of pending co-processor instructions have been executed by the co-processor.
In the following detailed description, the reader's attention is directed, in particular, to
FIGS. 1
to
7
and their associated description without intending to detract from the disclosure of the remainder of the description.
TABLE OF CONTENTS
1.0 Brief Description of the Drawings
2.0 List of Tables
3.0 Description of the Preferred and Other Embodiments
3.1 General Arrangement of Plural Stream Architecture
3.2 Host/Co-processor Queuing
3.3 Register Description of Co-processor
3.4 Format of Plural Streams
3.5 Determine Current Active Stream
3.6 Fetch Instruction of Current Active Stream
3.7 Decode and Execute Instruction
3.8 Update Registers of Instruction Controller
3.9 Semantics of the Register Access Semaphore
3.10 Instruction Controller
3.11 Description of a Modules Local Register File
3.12 Register Read/Write Handling
3.13 Memory Area Read/Write Handling
3.14 CBus Structure
3.15 Co-processor Data Types and Data Manipulation
3.16 Data Normalization Circuit
3.17 Image Processing Operations of Accelator Card
3.17.1 Compositing
3.17.2 Color Space Conversion Instructions
a.
Single Output General Color Space (SOGCS)
Conversion Mode
b.
Multiple Output General Color Space Mode
3.17.3 JPBG Coding/Decoding
a.
Encoding
b.
Decoding
3.17.4 Table Indexing
3.17.5 Data Coding Instructions
3.17.6 A Fast DCT Apparatus
3.17.7 Huffman Decoder
3.17.8 Image Transformation Instructions
3.17.9 Convolution Instructions
3.17.10 Matrix Multiplication
3.17.11 Halftoning
3.17.12 Hierarchial Image Format Decompression
3.17.13 Memory Copy Instructions
a. General purpose data movement instructions
b. Local DMA instructions
3.17.14 Flow Control Instructions
3.18 Modules of the Accelerator Card
3.18.1 Pixel Organizer
3.18.2 MUV Buffer
3.18.3 Result Organizer
3.18.4 Operand Organizers B and C
3.18.5 Main Data Path Unit
3.18.6 Data Cache Controller and Cache
a.
Normal Cache Mode
b.
The Single Output General Color Space
Conversion Mode
c.
Multiple Output General Color Space
Conversion Mode
d.
JPEG Encoding Mode
e.
Slow JPEG Decoding Mode
f.
Matrix Multiplication Mode
g.
Disabled Mode
h.
Invalidate Mode
3.18.7 Input Interface Switch
3.18.8 Local Memory Controller
3.18.9 Miscellaneous Module
3.18.10 External Interface Controller
3.18.11 Peripheral Interface Controller
APPENDIX A - Microprogramming
APPENDIX B - Register tables
REFERENCES:
patent: 3883847 (1975-05-01), Frank
patent: 3971927 (1976-07-01), Speiser et al.
patent: 4296476 (1981-10-01), Ma
Canon Kabushiki Kaisha
Fitzpatrick ,Cella, Harper & Scinto
Follansbee John A.
LandOfFree
Coprocessor interface having pending instructions queue and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Coprocessor interface having pending instructions queue and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Coprocessor interface having pending instructions queue and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2467273