Method and apparatus for management of bit plane resources
View Patent ↗System and method for the management of bit plane resources are presented. Because of the scarcity of processing element (PE) memory in a SIMD architecture, it is important to ensure that it is used with optimal efficiency. The Invention discloses methods for managing PE memory at runtime such that nearly 100% utilization is achieved. The method employed allows memory to be allocated and deallocated in single bit plane increments. Runtime allocation and deallocation occurs continuously such that it is impossible to guarantee availability of contiguous blocks of PE memory. The method employed by the invention allows scattered bit planes to be used without the necessity of expending execution time to perform “garbage collection”.
1. A digital data processing system comprising:
a. an array of processing elements; having addressable data storage means; adapted to process bit plane data;
b. an allocation table comprising storage means for storing physical addresses;
c. means for conveying an image descriptor comprising a virtual address attribute and a size attribute, the virtual address and size attributes specifying the range of the allocation table positions, wherein the physical addresses of the bit planes comprising an image are stored; and
d. a sequencer configured to control processing of bit planes in the processor array, the sequencer generating at least one microinstruction in response to at least one image descriptor, the image descriptor representing a processor array image operand, the at least one microinstruction comprising one microinstruction for each bit plane of the image operand, each of the microinstructions comprising a physical address, wherein the physical address is generated by reading the allocation table at a generated virtual address, the generated virtual address being computed by increasing the virtual address attribute of the image descriptor by a count of 1 for each generated microinstruction.
2. The system of claim 1 , wherein the number of storage positions in the allocation table exceeds the number of bit planes comprising the processing array.
3. The system of claim 1 , wherein the image descriptor further comprises a sign attribute to indicate whether the image is to be processed as signed data.
4. The system of claim 1 , wherein the allocation table is configured to provide multiple simultaneous accesses.
5. The system of claim 1 , wherein the array is partitioned into multiple segments, each segment comprising a number of bit planes, and wherein the allocation table is partitioned into corresponding segments, each allocation table segment comprising storage means for storing physical addresses pertaining to one of the array segments.
6. The system of claim 1 , further providing first allocation means for allocating bit planes to an image, the first allocation means comprising a repository of physical addresses representing available bit planes, and wherein the allocation includes reading a physical address from the repository and writing the physical address to the allocation table.
7. The system of claim 6 ,wherein the repository is a FIFO memory.
8. The system of claim 6 , wherein the processing array is partitioned into multiple segments, each segment comprising a number of bit planes, and wherein the repository is partitioned into corresponding segments, each repository segment comprising storage means for storing physical addresses of one of the array segments.
9. The system of claim 6 , further comprising second allocation means for allocating bit planes to an unpopulated image, the image having no bit planes allocated to it, and the second allocation means performing the allocation in response to an image descriptor wherein the size attribute is 0 and further responding to a size control signal the size control signal indicating the number of bit planes to allocate.
10. The system of claim 6 , further comprising third allocation means for allocating bit planes to a partially populated image, the image having a number of bit planes allocated to it, and the third allocation means performing the allocation in response to an image descriptor, and further responding to a size control signal, and allocating an additional number of bit planes such that the image is populated with the number of bit planes indicated by a size control signal.
11. The system of claim 6 , further comprising a scoreboard, the scoreboard comprising an array of registers equal in number to the number of allocation table positions, wherein each register is adapted to indicate whether the corresponding allocation table position is populated.
12. The system of claim 11 , further comprising detecting means for detecting the condition wherein an allocation is attempted for an allocation table position that is populated, and generating a signal to indicate the condition, and further including response means for responding to the signal to prevent the allocation until the condition is no longer detected.
13. The system of claim 11 , further comprising detecting means for detecting the condition wherein an allocation is attempted for an allocation table position that is populated, and generating a signal to indicate the condition, and further including means for setting an event register in response to the signal.
14. The system of claim 11 , wherein the allocation table is partitioned into multiple segments, each segment comprising a number of storage positions, and wherein the scoreboard is partitioned into corresponding segments, each scoreboard segment comprising an array of registers adapted to indicate allocation status for positions within the corresponding segment of the allocation table.
15. The system of claim 1 , further providing first deallocating means for deallocating bit planes of an image, the first deallocating means comprising a repository of physical addresses representing available bit planes, and wherein the deallocation includes reading a physical address from the allocation table and writing the physical address to the repository.
16. The system of claim 15 , wherein the repository is a FIFO memory.
17. The system of claim 15 , wherein the processing array is partitioned into multiple segments, each segment comprising a number of bit planes, and wherein the repository is partitioned into corresponding segments, each repository segment comprising storage means for storing physical addresses of one of the array segments.
18. The system of claim 15 , further comprising second deallocating means for deallocating bit planes of a populated image, the second deallocating means performing the deallocation in response to an image descriptor, and further responding to a free control signal, the free control signal indicating that all bit planes of the image are to be deallocated.
19. The system of claim 15 , further comprising third deallocating means for deallocating bit planes of a populated image, the third deallocating means performing the deallocation in response to an image descriptor, and further responding to a size control signal, and deallocating a number of bit planes such that the image is populated with the number of bit planes.
20. The system of claim 15 , further comprising a scoreboard, the scoreboard comprising an array of registers equal in number to the number of allocation table positions, wherein each register is adapted to indicate whether the corresponding allocation table position is populated.
21. The system of claim 20 , further comprising detecting means for detecting the condition wherein a deallocation is attempted for an allocation table position that is unpopulated, and generating a signal to indicate the condition, and further including response means for responding to the signal to prevent the deallocation until the condition is no longer detected.
22. The system of claim 20 , further comprising detecting means for detecting the condition wherein a deallocation is attempted for an allocation table position that is unpopulated, and generating a signal to indicate the condition, and further including means for setting an event register in response to the signal.
23. The system of claim 20 , wherein the allocation table is partitioned into multiple segments, each segment comprising a number of storage positions, and wherein the scoreboard is partitioned into corresponding segments, each scoreboard segment comprising an array of registers adapted to indicate allocation status for positions within the corresponding segment of the allocation table.
24. The system of claim 1 , further comprising processing means for processing an instruction, the instruction comprising at least one image descriptor, and further comprising a size control to determine the number of bit planes with which an image is to be populated as a result of processing the instruction.
25. The system of claim 24 , further comprising replacing means for replacing the size attribute with the value of the size control in a stored copy of the image descriptor.
26. The system of claim 1 , further comprising processing means for processing an instruction, the instruction comprising at least one image descriptor, and further comprising at least one free control to determine that all bit planes with which an image is populated are to be deallocated as a result of processing the instruction.