Computer architecture with a hardware accumulator reset
Summary by NHIP
Hardware Accumulator Reset
The processor executes nested loops to scan image patches while resetting accumulators upon loop termination. This process avoids breaking pipelined execution by distinguishing zero overhead loop hardware from address generation units and sending break signals only at outermost loop ends.
Claim Score by NHIP
Abstract
A processor with an accumulator. An event is selected to produce one or more selected events. A reset signal to the accumulator is generated responsive to the selected event. Responsive to the reset signal, the accumulator is reset to zero or another initial value while avoiding breaking pipelined execution of the processor.

Term
5.8 yearsleft in the term
Expires 25 July 2032.
- Priority
- Filed
- Granted
- Today
- Expires
11 claims: 2 independent, 9 dependent
- 1Broadest claimClaim Score 37, narrow(NHIP)A method performable by a processor, the method comprising:executing by the processor multiple nested loops for scanning multiple dimensions of image patches;wherein the multiple nested loops comprises multiple innermost loops and outermost loops;wherein the processor comprises a flow control unit, multiple accumulators, multiple address generation units, and multiple zero overhead loop units;wherein an execution of each nested loop of the multiple nested loop comprises:checking, by a zero overhead loop hardware allocated to an execution of the nested loop, a fulfillment of an end of dimension condition that is indicative of an end of a scanning of a dimension of the multiple dimensions;wherein the zero overhead loop hardware differs from an address generation unit allocated to the execution of the nested loop;sending a break out of nested loop signal to the flow control unit only at an end of an outermost loop of the nested loop;andbreaking out of the nested loop, by the flow control unit, responsive to the break out of nested loop signal.
- 5A system comprising:a processor including multiple accumulators, a flow control unit, multiple address generation units, and multiple zero overhead loop units;wherein the processor is configured to execute multiple nested loops for scanning multiple dimensions of image patches;wherein the multiple nested loops comprises multiple innermost loops and outermost loops;wherein an execution, by the processor of each each nested loop of the multiple nested loop comprises:checking, by a zero overhead loop hardware allocated to an execution of the nested loop, a fulfillment of an end of dimension condition that is indicative of an end of a scanning of a dimension of the multiple dimensions;wherein the zero overhead loop hardware differs from an address generation unit allocated to the execution of the nested loop;sending a break out of nested loop signal to the flow control unit only at an end of an outermost loop of the nested loop;andbreaking out of the nested loop, by the flow control unit, responsive to the break out of nested loop signal.
Independent claims2
99 paragraphs in 4 sections, as filed
BACKGROUND
1. Technical Field
The present invention relates to computer architecture.
2. Description of Related Art
During the last few years camera based driver assistance systems (DAS) have been entering the market; including lane departure warning (LDW), Automatic High-beam Control (AHC), pedestrian recognition, and forward collision warning (FCW). These driver assistance systems may use real time image processing of multiple patches detected in multiple image frames captured from a camera mounted in a vehicle.
Reduced instruction set computing is a processor design strategy based on a simplified instruction set and may provide higher performance if the simplicity enables much faster execution per instruction. A processor architecture based on this strategy is known herein as a reduced instruction set computer (RISC).
A vector processor, or array processor, is a processor that implements an instruction set containing instructions that operate on one-dimensional arrays of data called vectors. A scalar processor in comparison operates on a single datum. Most commonly used processors are scalar processors.
VLIW (Very Long Instruction Word) digital signal processing units contain several sub-processing units which operate in parallel. The VLIW contains multiple op-codes which direct the various sub-processing units, thus allowing for parallel processing since each sub-unit gets its op-code at the same time. An op-code is a portion of a machine language instruction that specifies an operation to be performed.
BRIEF SUMMARY
Thus, various embodiments of the present invention aim to reduce calculational overhead of image processing algorithms which may be used for instance in driver assistance systems.
Various methods are provided performable by a processor including an accumulator. Multiple events may be generated by the address generation unit (AGU), zero overhead loop circuit or other hardware circuit. An event is selected to produce one or more selected events. A reset signal to the accumulator is generated responsive to the selected event. Responsive to the reset signal, the accumulator is reset to zero or another initial value while avoiding breaking pipelined execution of the processor.
The events may be stored in an event register. The selection of the selected event may be performed by logically ANDing a first input from the event register with a second input from an event selection register to produce a first AND output including first multiple outputs. The first multiple outputs are logically ORed together to produce a first OR output. The reset signal to the accumulator is generated responsive to the first OR output.
The first OR output may be stored in a shift register. An output from the shift register is logically ANDed with an output of a stage selection register to produce a second AND output. The second AND output includes second multiple outputs. The stage selection register may specify a number of cycles after an event occurs for performing the reset. The second multiple outputs may be logically ORed together to produce a second OR output. The reset signal to the accumulator may be generated responsive to the second OR output. Multiple image patches may be input by an address generation unit (AGU) attached to the processor. The AGU may calculate memory addresses for the image patches. A processing loop for processing the image patches may be initiated. During the processing, the events are generated responsive to the memory addresses. While executing the processing loop, the accumulator may be reset responsive to the selected event. A number of cycles after the selected event may be specified. The reset of the accumulator may be generated after the specified number of cycles. After said at least one selected event, multiple numbers of cycles may be specified, e.g. a first number of cycles and a second number of cycles and resets of said accumulator may be generated after both the specified first number and second numbers of cycles.
Various methods are provided performable by a system including a camera adapted to capture multiple image frames. The system includes a processor with an accumulator. Multiple image patches from the image frames are input. A processing loop for processing the image patches is initiated. The accumulator is reset while executing the processing loop and breaking pipelined execution of the processor is avoidable. The processing of the image patches may be over multidimensional zero-overhead loops.
Various systems are provided including a processor with an accumulator. Logical circuitry selects an event to produce one or more selected events. The logical circuitry generates a reset signal to the accumulator responsive to the selected event. Responsive to the reset signal, the logical circuitry resets the accumulator to zero or another initial value while avoiding breaking pipelined execution of the processor. An address generation unit (AGU) may be attached to the processor, The events may generated by the address generation unit (AGU). A system may include a first address generation unit and a second address generation unit each configured to generate events. The first logical circuitry may receive the events generated by the first and second address generation units. A second logical circuitry may receive the events generated by the first and second address generation units. A first accumulator may connect to said first logical circuitry and a second accumulator may connect to said second logical circuitry. Responsive to the events, the first logical circuitry is configured to reset the first accumulator and the second logical circuitry is configured to reset the second accumulator.
The events may be stored in an event register. The selection of the selected event may be performed in a logical AND gate by logically ANDing with a first input from the event register and with a second input from an event selection register to produce a first AND output including first multiple outputs. In a logical OR gate, the first multiple outputs are logically ORed together to produce a first OR output. The reset signal to the accumulator may be generated responsive to the first OR output.
The first OR output may be stored in a shift register. The shift register may include bits which are shiftable to enable a history of cycles to be kept. An output from the shift register is logically ANDed with an output of a stage selection register to produce a second AND output. The second AND output includes second multiple outputs. The stage selection register is used by software of the processor to specify the number of cycles after an event is generated by the AGU to generate a reset of said accumulator.
The second multiple outputs may be logically ORed together to produce a second OR output. The reset signal to the accumulator may be generated responsive to the second OR output. The first and second OR outputs may be single bit outputs.
The foregoing and/or other aspects will become apparent from the following detailed description when considered in conjunction with the accompanying drawing figures.
BRIEF DESCRIPTION OF THE DRAWINGS
The invention is herein described, by way of example only, with reference to the accompanying drawings, wherein:
<figref idref="DRAWINGS">FIGS. 1 and 2</figref> illustrate a system including a camera or image sensor mounted in a vehicle, according to an aspect of the present invention.
<figref idref="DRAWINGS">FIG. 3</figref> illustrates a system block diagram for an image processing system, according to an embodiment of the present invention.
<figref idref="DRAWINGS">FIG. 4<i>a </i></figref>illustrates a simplified system for resetting accumulators, according to a feature of the present invention.
<figref idref="DRAWINGS">FIG. 4<i>b </i></figref>illustrates another simplified system for resetting accumulators, according to a feature of the present invention.
<figref idref="DRAWINGS">FIG. 5</figref> shows a hardware implementation of an accumulator reset, according to a feature of the present invention.
<figref idref="DRAWINGS">FIG. 6<i>a </i></figref>shows a method and <figref idref="DRAWINGS">FIG. 6<i>b </i></figref>which shows a method which may be a continuation of the method of <figref idref="DRAWINGS">FIG. 6<i>a</i></figref>, according to a feature of the present invention.
<figref idref="DRAWINGS">FIG. 7</figref> shows a method, according to a feature of the present invention.
DETAILED DESCRIPTION
Reference will now be made in detail to features of the present invention, examples of which are illustrated in the accompanying drawings, wherein like reference numerals refer to the like elements throughout. The features are described below to explain the present invention by referring to the figures.
Before explaining features of the invention in detail, it is to be understood that the invention is not limited in its application to the details of design and the arrangement of the components set forth in the following description or illustrated in the drawings. The invention is capable of other features or of being practiced or carried out in various ways. Also, it is to be understood that the phraseology and terminology employed herein is for the purpose of description and should not be regarded as limiting.
Embodiments of the present invention are applicable to processors designed for driver assistance systems, and other applications in digital processing for instance other image processing applications and/or audio processing applications.
By way of introduction, the basic concept of pipelined processing is to divide instruction execution into stages that operate independently. In pipelined execution, instructions may pass through the same stages as in an assembly line. With each new processor cycle, a new piece of data may be added to one end of the pipeline and a completed result may be retired out of the other end of the pipeline. Embodiments of the present invention are directed reducing calculational overhead with the use of digital logic circuitry for resetting an accumulator of a processor in real time. Resetting accumulators may be performed while executing a loop in hardware while avoiding breaking out of pipelined execution.
The terms “pipelining”, “pipelined processing” “pipelined execution as used herein refers to a technique used in advanced microprocessors in which the processor begins executing a second instruction before the first has been completed. That is, several instructions are in the pipeline simultaneously, each at a different processing stage. The pipeline may be divided into segments and each segment may execute its operation concurrently with other segments. When a segment completes an operation, the result is passed to the next segment in the pipeline and the next operation is fetched from the preceding segment. The terms “pipelining” and “pipelined processing” and “pipelined execution” are used herein interchangeably.
The resetting of accumulators according to aspects of the present invention may find use in zero-overhead loops for given small/narrow image patches (from captured image frames) that are common in computer vision systems such as driver assistance systems (DASs). The resetting of accumulators may prevents the need to break out of a multidimensional zero-overhead loops (ZOLs) (or break pipelining) “just” to reset an accumulator. The resetting of accumulators according to embodiments of the present invention typically may expand the utility of multidimensional ZOLs.
The terms logical “AND”, “ANDing” or “ANDed” as used herein refer to the function of a digital AND gate which logically ANDs together variables at the input to give at least one variable at the output.
The terms logical “OR”, “ORing” or “ORed” as used herein refer to the function of a digital OR gate which logically ORs together variables at the input to give at least one variable at the output.
Definition of “Accumulator”
Basically, in the context of accumulator reset according to features of the present invention, the term “accumulator” as used herein is a device which maintains a state. The state may be updated by an “accumulation instruction”, which, in turn, is any instruction which functionally performs as: <br />state=function (state, inputs)
The most common accumulation function is addition: state=state+input
Vector accumulation may be reducing, non-reducing, or cumulative:
<tables id="TABLE-US-00001" num="00001"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="1"><colspec colname="1" colwidth="217pt" align="left" /><thead><row><entry namest="1" nameend="1" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry>state = state + sum(input_vector) # reducing − 8+1 arguments, 1 result</entry></row><row><entry>for i=0:8, state_vector[i] = state_vector[i] + input_vector[i] #</entry></row><row><entry>non-reducing − 8+8 arguments, 1 result</entry></row><row><entry>prev_sum=state_vector[7]; for i=0:8, state_vector[i] = prev_sum +</entry></row><row><entry>sum(input_vector for 0 to i) # cumulative</entry></row><row><entry namest="1" nameend="1" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>
Another interesting case is when the function is other than/addition:
<tables id="TABLE-US-00002" num="00002"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="1" colwidth="21pt" align="left" /><colspec colname="2" colwidth="196pt" align="left" /><thead><row><entry namest="1" nameend="2" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /><entry>state = min(state,input)</entry></row><row><entry /><entry>state = max(state,input)</entry></row><row><entry /><entry>for i=0:8,</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="1" colwidth="35pt" align="left" /><colspec colname="2" colwidth="182pt" align="left" /><tbody valign="top"><row><entry /><entry>state_histogram[input_index[i]] =</entry></row><row><entry /><entry>state_histogram[input_index[i]] + input_weight[i]]</entry></row><row><entry namest="1" nameend="2" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>
All these examples herein above are “accumulators” in the sense that accumulator resets according to different features of the present invention may be applied to the accumulators.
“Pipelining” in General Versus “Software Pipelining” in VLIW Machines
In general, accumulator reset according to features of the present invention may not be particularly useful on any processor just because the processor is pipelined. For example, consider the loop:
<tables id="TABLE-US-00003" num="00003"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="1" colwidth="77pt" align="left" /><colspec colname="2" colwidth="140pt" align="left" /><thead><row><entry namest="1" nameend="2" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /><entry>for y=0:H {</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="1" colwidth="91pt" align="left" /><colspec colname="2" colwidth="126pt" align="left" /><tbody valign="top"><row><entry /><entry>acc=0</entry></row><row><entry /><entry>for x=0:W {</entry></row><row><entry /><entry>acc+=img(x,y)</entry></row><row><entry /><entry>}</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="1" colwidth="77pt" align="left" /><colspec colname="2" colwidth="140pt" align="left" /><tbody valign="top"><row><entry /><entry>}</entry></row><row><entry namest="1" nameend="2" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>
On a pipelined RISC processor, resetting the accumulator in software creates an overhead, but a relatively small one:
<tables id="TABLE-US-00004" num="00004"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="1"><colspec colname="1" colwidth="217pt" align="left" /><thead><row><entry namest="1" nameend="1" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry>YLOOP:</entry></row><row><entry>SET ACC,0</entry></row><row><entry>XLOOP:</entry></row><row><entry>LOAD R0,img_next_addr //it would be more instructions, but let's</entry></row><row><entry>ignore it here</entry></row><row><entry>ADD ACC,R0</entry></row><row><entry>BEQ X,W, XLOOP //end XLOOP</entry></row><row><entry>BEQ Y,H, YLOOP</entry></row><row><entry namest="1" nameend="1" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>
Suppose W=8 which means that every 8 iterations, one instruction is spent—SET ACC,0—to reset the accumulator. If every iteration costs 3 instructions—LOAD, ADD, BEQ—that is 1 instruction of “overhead” for 24 instructions of “useful work”—not that much. Furthermore, it does not matter much whether the processor is pipelined or not, at least it does not matter in any straightforward way. A pipelined RISC processor will or at least could execute all these instructions in a pipelined fashion—whether there is a SET ACC, 0 instruction occasionally being executed or not.
The overhead is much larger on VLIW machines, however, and not because of pipelining in general, but because of, specifically, software pipelining. On a VLIW machine, the loop would look like this:
<tables id="TABLE-US-00005" num="00005"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="1"><colspec colname="1" colwidth="217pt" align="left" /><thead><row><entry namest="1" nameend="1" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry>YLOOP:</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="1" colwidth="42pt" align="left" /><colspec colname="2" colwidth="175pt" align="left" /><tbody valign="top"><row><entry>SET ACC,0</entry><entry>//X loop header assuming LOAD latency is 2 cycles, so we</entry></row><row><entry /><entry>can't ADD anything for the first 2 cycles</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="1"><colspec colname="1" colwidth="217pt" align="left" /><tbody valign="top"><row><entry>LOAD R0,img_next_addr</entry></row><row><entry>LOAD R0,img_next_addr</entry></row><row><entry>XLOOP:</entry></row><row><entry>LOAD R0,img_next_addr *AND IN PARALLEL* ADD ACC,R0//X</entry></row><row><entry>loop trailer handle values loaded by the last 2 loads</entry></row><row><entry>ADD ACC,R0</entry></row><row><entry>ADD ACC R0</entry></row><row><entry namest="1" nameend="1" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>
On VLIW machines, pipelining is handled differently than, say, on RISC machines. Specifically, pipelining effects are visible to software: on a RISC machine, all instructions following LOAD R0. . . can assume R0 has the new value—not so on VLIW, where the ADD using the result of the LOAD should be placed two instructions down the road. The result of the LOAD placed two instructions down the road, has the benefit of simplifying hardware: a VLIW processor can issue multiple instructions at the same cycle—like in the example above, where LOAD and ADD are done, in the loop though not in the header or the trailer, simultaneously. A RISC processor can also place the result of the load two instructions down the road—super-scalar/out-of-order processors with RISC instruction sets do this but the cost is relatively complicated hardware mechanisms that analyze, at run-time, the dependencies between the instructions that RISC processors execute in order to figure out how to run the instructions in parallel, and whether it is at all logically possible to run the instructions in parallel.
The upshot is that VLIW with ZOLs, speed up the innermost loops significantly—there's one instruction instead of 3 or more—without complicating the hardware (as does a super-scalar processor that could actually run 3 instructions, or more, in parallel).
Now consider the overhead of resetting an accumulator on a VLIW machine compared to a single-issue RISC machine. Not only is one cycle per every 8 instructions paid—⅛ is more than 1/24—but a price is also paid for the header and the trailer. In our example, that is 2 cycles for the header and 2 cycles for the trailer—overall, 5 (1+2+2) cycles of overhead for 8 cycles of useful work.
Therefore, accumulator reset according to features of the present invention is particularly advantageous on a VLIW processor.
Reference is now made to <figref idref="DRAWINGS">FIGS. 1 and 2</figref> which illustrate a system <b>16</b> including a camera or image sensor <b>12</b> mounted in a vehicle <b>18</b>, according to an aspect of the present invention. Image sensor <b>12</b>, imaging a field of view in the forward direction provides image frames <b>15</b> in real time and image frames <b>15</b> are captured by an image processor <b>14</b>. Image processor <b>14</b> may be used to process image frames <b>15</b> simultaneously and/or in parallel to serve a number of driver assistance systems/applications. The driver assistance systems may be implemented using specific hardware circuitry with on board software and/or software control algorithms in storage <b>13</b>. Image sensor <b>12</b> may be monochrome or black-white, i.e. without color separation or image sensor <b>12</b> may be color sensitive. By way of example in <figref idref="DRAWINGS">FIG. 2</figref>, image frames <b>15</b> are used to serve pedestrian detection <b>20</b>, traffic sign recognition (TSR) <b>21</b> and forward collision warning (FCW) <b>22</b>. Image processor <b>14</b> is used to process image frames <b>15</b> to detect and recognize an image or portions of the image in the forward field of view of camera <b>12</b>.
Driver assistance systems may further include lane departure warning systems and headlight control systems. Most driver assistance applications require processing over multiple windows of a single frame and/or multiple image frames. In some cases, image frames <b>15</b> are partitioned between different driver assistance applications and in other cases the image frames <b>15</b> are shared between the different driver assistance applications.
Reference is now made to <figref idref="DRAWINGS">FIG. 3</figref> which illustrates a system block diagram for an image processing system <b>30</b> according to an embodiment of the present invention. Image processing system <b>30</b> includes a vector processor <b>304</b> and a memory <b>302</b>. Memory <b>302</b> connects to an input of multiple image frames <b>15</b> via an image frame bus <b>310</b>. Vector processor <b>304</b> includes multiple arithmetic logic units (ALU) <b>320</b> and multiple address generators <b>308</b> which connect to multiple accumulators resets <b>306</b> via event line <b>32</b>. Multiple zero overhead (ZOL) modules <b>362</b> are connected to flow control <b>340</b> and multiple accumulators resets <b>306</b>. Address generators <b>308</b> connect to memory <b>302</b> with a memory bus <b>331</b>. Address generators <b>308</b> also connect to flow controller <b>340</b> which provides a flow control line <b>342</b> to multiple accumulators resets <b>306</b>. Arithmetic logic units (ALU) <b>320</b> and address generator <b>308</b> connect to a very long instruction word (VLIW) instruction register <b>322</b> via their own separate buses (thus allowing simultaneous execution of the relevant op-codes. ALUs <b>320</b> have accumulators <b>36</b> which are resettable via accumulators resets <b>306</b> through accumulator reset line <b>34</b>.
With traditional DSP-style zero-overhead loops (ZOLs), a machine repeatedly runs a piece of code, decrementing a counter until the counter becomes zero. At first glance, the counter works with rectangles from image patches or 1 dimensional (1D) arrays. Suppose a 1D array of size N takes N/8 iterations to process as may take place on a single instruction multiple data (SIMD) machine processing 8 data items at a time for example. So the ZOL counter is set to N/8. For a 2D rectangle of width W and height H, W*H/8 iterations are needed. A question may arise as to why not set the counter to W*H/8, and use ZOL as with 1D arrays? An answer to the question is the possible problem in maintaining X & Y coordinates. With ID arrays, there is a ID coordinate called i that gets the values, assuming increments of 8:
<tables id="TABLE-US-00006" num="00006"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="1" colwidth="98pt" align="left" /><colspec colname="2" colwidth="119pt" align="left" /><thead><row><entry namest="1" nameend="2" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /><entry>i=0</entry></row><row><entry /><entry>i=8</entry></row><row><entry /><entry>...</entry></row><row><entry /><entry>i=N</entry></row><row><entry namest="1" nameend="2" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>
With 2D coordinates, X and Y, every time the end of a rectangle's row is reached, there is a special case:
<tables id="TABLE-US-00007" num="00007"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="1" colwidth="42pt" align="left" /><colspec colname="2" colwidth="175pt" align="left" /><thead><row><entry namest="1" nameend="2" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /><entry>X=0, Y=0 //next, increment X...</entry></row><row><entry /><entry>X=8, Y=0 //next, increment X...</entry></row><row><entry /><entry>...</entry></row><row><entry /><entry>X=W, Y=0 //NOW, increment Y and reset X</entry></row><row><entry /><entry>X=0, Y=1 //next, increment X</entry></row><row><entry /><entry>...</entry></row><row><entry /><entry>X=W, Y=1 //NOW, increment Y and reset X</entry></row><row><entry /><entry>X=0, Y=1 //next, increment X</entry></row><row><entry namest="1" nameend="2" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>
The special case is handled by special code in the program, so it may not be possible to just run the same code W*H/8 times using a ZOL iteration counter. Similar issues may occur with 3D arrays, 4D arrays, etc., which may mean only the innermost dimension can be implemented using a traditional DSP ZOL and the outer dimensions become regular loops. For example:
<tables id="TABLE-US-00008" num="00008"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="1" colwidth="63pt" align="left" /><colspec colname="2" colwidth="154pt" align="left" /><thead><row><entry namest="1" nameend="2" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /><entry>for Y: //regular loop</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="1" colwidth="77pt" align="left" /><colspec colname="2" colwidth="140pt" align="left" /><tbody valign="top"><row><entry /><entry>for X: //a DSP-style ZOL</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="1" colwidth="91pt" align="left" /><colspec colname="2" colwidth="126pt" align="left" /><tbody valign="top"><row><entry /><entry>body</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="1" colwidth="77pt" align="left" /><colspec colname="2" colwidth="140pt" align="left" /><tbody valign="top"><row><entry /><entry>X=0, Y++ //special case</entry></row><row><entry namest="1" nameend="2" align="center" rowsep="1" /></row></tbody></tgroup></table></tables><br /> Or, with 3D data, and different nesting—X is the outermost loop:
<tables id="TABLE-US-00009" num="00009"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="1" colwidth="56pt" align="left" /><colspec colname="2" colwidth="161pt" align="left" /><thead><row><entry namest="1" nameend="2" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /><entry>for X: //regular loop</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="1" colwidth="70pt" align="left" /><colspec colname="2" colwidth="147pt" align="left" /><tbody valign="top"><row><entry /><entry>for Y: //regular loop</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="1" colwidth="84pt" align="left" /><colspec colname="2" colwidth="133pt" align="left" /><tbody valign="top"><row><entry /><entry>for Z: //a DSP-style ZOL</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="1" colwidth="98pt" align="left" /><colspec colname="2" colwidth="119pt" align="left" /><tbody valign="top"><row><entry /><entry>body</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="1" colwidth="84pt" align="left" /><colspec colname="2" colwidth="133pt" align="left" /><tbody valign="top"><row><entry /><entry>Z=0, Y++ //special case</entry></row><row><entry namest="1" nameend="2" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>
Where the innermost dimension is implemented using a traditional DSP ZOL there may not be a problem when the innermost loop executes many times, but may become a problem when the inner loop executes just a few times. This way, the innermost loop is in fact “zero-overhead”—but the frequently executing outer loops are not zero-overhead. So there are significant overheads associated with breaking pipelined execution of the inner loops that traditional ZOLs with ID data do not eliminate. These overheads arc especially large for very large instruction word (VLIW) machines. SIMD and VLIW are basically orthogonal, there are SIMD VLIW machines, SIMD machines that are not VLIW, and VLIW machines that are not SIMD. Vector microcode processor (VMP) is both SIMD and VLIW, a prominent example of a SIMD VLIW machine is TI's C64 family for example.
In contrast to SIMD VLIW machines, vector processor <b>304</b> address generation units (AGUs) <b>308</b> allow use of a single ZOL by: <ul id="ul0001" list-style="none"><li id="ul0001-0001" num="0000"><ul id="ul0002" list-style="none"><li id="ul0002-0001" num="0064">Taking care of the special case—end-of-innermost-dimension—automatically in hardware. Every time an AGU <b>308</b> is issued a “next” command, the hardware checks for end-of-dimension conditions.</li><li id="ul0002-0002" num="0065">Raising a “break out of the loop” signal for flow control unit <b>340</b> only at the end of the outermost loop (when so configured).</li></ul></li></ul>
For example, a loop over 3D data can look like this:
<tables id="TABLE-US-00010" num="00010"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="1"><colspec colname="1" colwidth="217pt" align="left" /><thead><row><entry namest="1" nameend="1" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry>my_iter=Iterator3D(base=..., xcount=..., ycount=..., zcount=...);</entry></row><row><entry>iterate { //a single ZOL</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="1" colwidth="14pt" align="left" /><colspec colname="2" colwidth="203pt" align="left" /><tbody valign="top"><row><entry /><entry>data=my_iter.load( ); //takes care of end-of-dimension conditions,</entry></row><row><entry /><entry>breaks when all data is processed</entry></row><row><entry /><entry>...</entry></row><row><entry /><entry>}</entry></row><row><entry namest="1" nameend="2" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>
As explained above, it may be beneficial to stay inside a ZOL for as long as possible. An example of an overhead avoidable using a feature of the present invention is breaking out of a ZOL. Every time a break out occurs, loop trailer code is executed and every time a loop is re-entered, loop header code is executed by ZOL module <b>362</b>.
AGUs <b>308</b> of vector processor <b>304</b> communications to flow control unit <b>340</b> are beneficial because their need to handle end-of-row conditions is eliminated. AGUs <b>308</b> of vector processor <b>304</b> communications to flow control unit <b>340</b> are beneficial also because the loop is entered and only quit at the end of the 2D region, not at the end of every row.
At the beginning of every row X is reset to its minimal coordinate and Y is incremented to the next row which may be handled by AGU <b>308</b> without needing to break out of the loop. We would, however, break out of the innermost loop over rows if something special is done at the beginning of every row. One of the most common things to be done at the beginning of rows is resetting an accumulator <b>36</b>. For a simple example, consider a horizontal integral image where
<tables id="TABLE-US-00011" num="00011"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="1" colwidth="42pt" align="left" /><colspec colname="2" colwidth="175pt" align="left" /><thead><row><entry namest="1" nameend="2" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /><entry>out (x, y) = sum (in(1: x, y)):</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="1" colwidth="56pt" align="left" /><colspec colname="2" colwidth="161pt" align="left" /><tbody valign="top"><row><entry /><entry>for y:</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="1" colwidth="70pt" align="left" /><colspec colname="2" colwidth="147pt" align="left" /><tbody valign="top"><row><entry /><entry>acc = 0</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="1" colwidth="56pt" align="left" /><colspec colname="2" colwidth="161pt" align="left" /><tbody valign="top"><row><entry /><entry>for x:</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="1" colwidth="70pt" align="left" /><colspec colname="2" colwidth="147pt" align="left" /><tbody valign="top"><row><entry /><entry>acc += in(x,y) // acc:=acc+in(x,y)</entry></row><row><entry /><entry>out(x,y) = acc</entry></row><row><entry namest="1" nameend="2" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>
In this loop above, the same operation is done for all pixels in all rows, except for zeroing the accumulator <b>36</b> at the beginning. Therefore, if there is no accumulator reset, nested loops are used along the lines of:
<tables id="TABLE-US-00012" num="00012"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="1"><colspec colname="1" colwidth="217pt" align="left" /><thead><row><entry namest="1" nameend="1" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry>iterate {</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="1" colwidth="14pt" align="left" /><colspec colname="2" colwidth="203pt" align="left" /><tbody valign="top"><row><entry /><entry>A.reset( );</entry></row><row><entry /><entry>iterate {</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="1" colwidth="28pt" align="left" /><colspec colname="2" colwidth="189pt" align="left" /><tbody valign="top"><row><entry /><entry>in=in_iter.load( );</entry></row><row><entry /><entry>low,hi=A.cumsum_8ub_8uh(in); //vectorized cumulative sum</entry></row><row><entry /><entry>out_iter.store(low,hi);</entry></row><row><entry /><entry>}</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="1" colwidth="14pt" align="left" /><colspec colname="2" colwidth="203pt" align="left" /><tbody valign="top"><row><entry /><entry>}</entry></row><row><entry namest="1" nameend="2" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>
In vector processor <b>304</b>, accumulator reset can be used to create a single loop:
<tables id="TABLE-US-00013" num="00013"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="1" colwidth="14pt" align="left" /><colspec colname="2" colwidth="203pt" align="left" /><thead><row><entry namest="1" nameend="2" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /><entry>iterate {</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="1" colwidth="28pt" align="left" /><colspec colname="2" colwidth="189pt" align="left" /><tbody valign="top"><row><entry /><entry>in=in_iter.load( );</entry></row><row><entry /><entry>low,hi=A.cumsum_8ub_8uh(in,acc_reset=(in_iter,i));</entry></row><row><entry /><entry>out_iter.store(low,hi);</entry></row><row><entry /><entry>}</entry></row><row><entry namest="1" nameend="2" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>
Vector processor <b>304</b> instructs the hardware to behave as follows. An event is signaled to the accumulator reset <b>306</b> every time the iterator in_iter reaches the end of its innermost loop (the loop over rows may be the innermost or it could be the loop over columns instead, depending on the programming of the iterator which is omitted from the example). Upon that event, the accumulator reset <b>306</b> zeros the accumulator <b>36</b> such that instead of updating the accumulator <b>36</b> as usual, the accumulator reset <b>306</b> resets the accumulator <b>36</b> and then updates the accumulator <b>36</b>.
The description above is different from simply resetting the accumulator <b>36</b>—that would be incorrect. For example, the need to compute the cumulative sum of the first 8 pixels in the row (just as well as the second 8-pixel tuple, then third, etc.), and resetting the accumulator <b>36</b> instead would get the first 8 pixels ignored. So accumulator reset <b>306</b> modifies the behavior of the cumsum instruction to the semantics, “reset the accumulator <b>36</b>, then do your job as usual”. This is also how the accumulator reset works with other accumulation instructions—plain vectorized accumulation, dimension-reducing accumulation, etc.]
Reference is now made to <figref idref="DRAWINGS">FIGS. 4<i>a </i>and 4<i>b </i></figref>which show different signaling schemes using two accumulators (not shown each in ALU <b>320</b> and a single accumulator reset (acc_reset) <b>306</b>, according to features of the present invention. The terms” accumulator reset <b>306</b> and logical circuitry <b>306</b> are used herein interchangeably.
Referring specifically to <figref idref="DRAWINGS">FIG. 4<i>a</i></figref>, single accumulator reset (acc_reset) <b>306</b> may receive an event from AGU <b>308</b><i>a</i>, AGU <b>308</b><i>b </i>via respective event lines <b>32</b><i>a </i>or <b>32</b><i>b </i>and/or from multiple ZOL modules <b>362</b>. In general the event comes from a place which is not the normally used instruction fetch/decode hardware. The event may occur at the beginning of a row, the end of a row or the last point in the image patches from captured image frames <b>15</b>. The event typically encodes an AGU <b>308</b> number (so that an event can come from any of the 2 AGUs <b>308</b><i>a </i>or <b>308</b><i>b </i>used in this example found in vector processor <b>304</b>) and the location in the 2/3/4D region of the image patches which upon reaching the event is signaled. The event can then be scheduled to provide a reset from accumulator reset <b>306</b> via reset lines <b>34</b> because some operations within vector processor <b>304</b> need the reset, some do not, and each operation happens at a different delay. Therefore at some point at a beginning-of-row or some other special iteration—and “at this point in time”, an event is signaled that modifies the behavior of accumulator reset <b>306</b>. In reality, however, the AGU <b>308</b> will reach that iteration earlier than the accumulator reset due to modulo scheduling. Modulo Scheduling, another name for pipe-lining, is a form of instruction scheduling that interleaves different iterations of a loop. Based on the event flow controller <b>340</b> enables the reset from accumulator reset <b>306</b> to be applied to either accumulator <b>36</b><i>a </i>of ALU <b>320</b><i>a </i>and/or accumulator <b>36</b><i>b </i>of ALU <b>320</b><i>b. </i>
In <figref idref="DRAWINGS">FIG. 4<i>b</i></figref>, AGU <b>308</b><i>a </i>or AGU <b>308</b><i>b </i>may have events provided to accumulator resets <b>306</b><i>a </i>and <b>306</b><i>b </i>via event lines <b>32</b><i>a</i>, <b>32</b><i>b</i>, <b>32</b><i>c</i>, <b>32</b><i>d </i>and/or from multiple ZOL modules <b>362</b>. Events from AGU <b>308</b><i>a </i>may be provided to accumulator resets <b>306</b><i>a </i>and/or <b>306</b><i>b. </i>Similarly events from AGU <b>308</b><i>b </i>may be provided to accumulator resets <b>306</b><i>a </i>and/or <b>306</b><i>b</i>. Resets from accumulator resets <b>306</b><i>a </i>and <b>306</b><i>b </i>via reset lines <b>34</b><i>a </i>and <b>34</b><i>b </i>respectively may be applied to respective accumulators <b>36</b><i>a </i>and <b>36</b><i>b </i>based on the events generated by AGU <b>308</b><i>a </i>and/or AGU <b>308</b><i>b. </i>
Reference is now made to <figref idref="DRAWINGS">FIG. 5</figref> which shows a hardware implementation of an accumulator reset <b>306</b>, according to a feature of the present invention. A number of events <b>32</b> are input into event register <b>502</b>. The output of event register <b>502</b> is E bits which correspond with the number of events <b>32</b> which is logically ‘ANDed’ together with the K bits of event selector register <b>504</b> via AND gate <b>510</b><i>a</i>. The K bit output of AND gate <b>510</b><i>a </i>is then inputted into OR gate <b>512</b><i>a</i>, where the K bits are ORed with each other, which gives a single bit output which is placed into history shift register <b>506</b>. The N bit output of history shift register <b>506</b> is then ‘ANDed’ with the N bits of stage selector <b>508</b> via AND gate <b>510</b><i>b</i>. The N bit output of AND gate <b>510</b><i>b </i>is then input into the N bit input of OR gate <b>512</b><i>b</i>, where the N bits are ORed with each other to give a single bit output. The single bit output of OR gate <b>512</b><i>a </i>may be the accumulator reset <b>34</b> shown in the previous figures.
At this point in the explanation, the utility of the features of the present invention should be clear, as well as the general way to achieve the utility of the features of the present invention. In further detail, the core hardware mechanisms that make the utility of the features of the present invention actually work is shown below in the many different contexts where the features are useful. In particular, two things are taken into account: <ul id="ul0003" list-style="none"><li id="ul0003-0001" num="0000"><ul id="ul0004" list-style="none"><li id="ul0004-0001" num="0083">Different event types. Vector processor <b>304</b> AGUs <b>308</b> support 2D, 3D and 4D regions. A programmer might want an accumulator to be reset, not necessarily at the beginning of every row, but at many kinds of special locations within the 2/3/4D region.</li><li id="ul0004-0002" num="0084">Scheduling delays. Logically, at some point at a beginning-of-row or some other special iteration—and “at this point in time”, an event is signaled that modifies the behavior of the accumulator. In reality, however, the AGU <b>308</b> will reach that iteration earlier than the accumulator due to modulo scheduling. Furthermore, some operations need the reset, some do not, and each happens at a different delay.</li></ul></li></ul>
Here is how the hardware described above and specifically hardware implementation of accumulator resets shown in <figref idref="DRAWINGS">FIG. 5</figref> handles these concerns.
Different Event Types
In vector processor <b>304</b>, a hardware register called event selector register <b>504</b> keeps an event number, so that an accumulator reset <b>306</b> responds to an event chosen by the programmer. The event number encodes the AGU <b>308</b> number (so that an event can come from any of the 4 AGUs <b>308</b> used in this example found in vector processor <b>304</b>) and upon reaching the location in the 2/3/4D region an event is signaled. Specifically, vector processor <b>304</b> supports the following locations according to a list (the list could be extended—the locations were chosen based on the assumption that in vector microcode processor programs, these are the particularly useful locations):
In the list, bold names name location types, and non-bold i, z and w name internal AGU <b>308</b> counters corresponding to the current location. z is the location along the Z (3rd) region dimension, w is the location along the W (4th) region dimension, and i is the location of either the X (1st) or Y (2nd) dimension, depending on which of them is the innermost dimension—in a “for y {for x}” loop, i is the X dimension counter, and in a “for x {for y}” loop, i is the Y dimension counter. <ul id="ul0005" list-style="none"><li id="ul0005-0001" num="0000"><ul id="ul0006" list-style="none"><li id="ul0006-0001" num="0088">i—This condition will raise iff (i==0 & z==0 & w==0)—that is, once every time i reaches 0</li><li id="ul0006-0002" num="0089">z—This condition will raise iff (z==0 & w==0)—that is, once every time z reaches 0</li><li id="ul0006-0003" num="0090">w—This condition will raise iff w==0—that is, once every time w reaches 0</li><li id="ul0006-0004" num="0091">iz—This condition will raise iff i==0—that is, when i reaches 0, through all z iterations</li><li id="ul0006-0005" num="0092">zw—This condition will raise iff z==0—that is, when z reaches 0, through all w iterations</li></ul></li></ul>
The following pseudo-code illustrates when each of these events “fire” given an AGU <b>308</b> iterating over a 4D region such that X is the outermost dimension (it should be noted that AGUs <b>308</b> of vector processor <b>304</b> support either X or Y as their outermost region dimension, but not Z or W-Z is always nested in either X or Y, and W is always nested in Z; this explains why some of the obvious conditions that one could imagine are not available.)
<tables id="TABLE-US-00014" num="00014"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="1"><colspec colname="1" colwidth="217pt" align="left" /><thead><row><entry namest="1" nameend="1" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry>void izw(int xcount, int ycount, int zcount, int wcount) {</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="1" colwidth="14pt" align="left" /><colspec colname="2" colwidth="203pt" align="left" /><tbody valign="top"><row><entry /><entry>int x,y,z,w;</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="1" colwidth="28pt" align="left" /><colspec colname="2" colwidth="189pt" align="left" /><tbody valign="top"><row><entry /><entry>for(x=0; x<xcount; ++x) {</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="1" colwidth="42pt" align="left" /><colspec colname="2" colwidth="175pt" align="left" /><tbody valign="top"><row><entry /><entry>for(y=0; y<ycount; ++y) {</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="1" colwidth="56pt" align="left" /><colspec colname="2" colwidth="161pt" align="left" /><tbody valign="top"><row><entry /><entry>for(z=0; z<zcount; ++z) {</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="1" colwidth="70pt" align="left" /><colspec colname="2" colwidth="147pt" align="left" /><tbody valign="top"><row><entry /><entry>for(w=0; w<wcount; ++w) {</entry></row><row><entry /><entry>int i=y; //y is our inner dimension</entry></row><row><entry /><entry>printf(“x=%d y=%d z=%d w=%d”, x, y, z, w);</entry></row><row><entry /><entry>printf(i==0 && z==0 && w==0? “ i”: “ ”);</entry></row><row><entry /><entry>printf(z==0 && w==0? “ z”: “ ”);</entry></row><row><entry /><entry>printf(w==0? “ w”: “ ”);</entry></row><row><entry /><entry>printf(i==0? “ iz”: “ ”);</entry></row><row><entry /><entry>printf(z==0? “ zw”: “ ”);</entry></row><row><entry /><entry>printf(“\n”);</entry></row><row><entry /><entry>}</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="1" colwidth="56pt" align="left" /><colspec colname="2" colwidth="161pt" align="left" /><tbody valign="top"><row><entry /><entry>}</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="1" colwidth="42pt" align="left" /><colspec colname="2" colwidth="175pt" align="left" /><tbody valign="top"><row><entry /><entry>}</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="1" colwidth="28pt" align="left" /><colspec colname="2" colwidth="189pt" align="left" /><tbody valign="top"><row><entry /><entry>}</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="1" colwidth="14pt" align="left" /><colspec colname="2" colwidth="203pt" align="left" /><tbody valign="top"><row><entry /><entry>}</entry></row><row><entry namest="1" nameend="2" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>
This will print, given counts of 2 for all dimensions:
<tables id="TABLE-US-00015" num="00015"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="1" colwidth="63pt" align="left" /><colspec colname="2" colwidth="154pt" align="left" /><thead><row><entry namest="1" nameend="2" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /><entry>x=0 y=0 z=0 w=0 i z w iz zw</entry></row><row><entry /><entry>x=0 y=0 z=0 w=1 iz zw</entry></row><row><entry /><entry>x=0 y=0 z=1 w=0 w iz</entry></row><row><entry /><entry>x=0 y=0 z=1 w=1 iz</entry></row><row><entry /><entry>x=0 y=1 z=0 w=0 z w zw</entry></row><row><entry /><entry>x=0 y=1 z=0 w=1 zw</entry></row><row><entry /><entry>x=0 y=1 z=1 w=0 w</entry></row><row><entry /><entry>x=0 y=1 z=1 w=1</entry></row><row><entry /><entry>x=1 y=0 z=0 w=0 i z w iz zw</entry></row><row><entry /><entry>x=1 y=0 z=0 w=1 iz zw</entry></row><row><entry /><entry>x=1 y=0 z=1 w=0 w iz</entry></row><row><entry /><entry>x=1 y=0 z=1 w=1 iz</entry></row><row><entry /><entry>x=1 y=1 z=0 w=0 z w zw</entry></row><row><entry /><entry>x=1 y=1 z=0 w=1 zw</entry></row><row><entry /><entry>x=1 y=1 z=1 w=0 w</entry></row><row><entry /><entry>x=1 y=1 z=1 w=1</entry></row><row><entry namest="1" nameend="2" align="center" rowsep="1" /></row></tbody></tgroup></table></tables><br /> Scheduling Delays
In order to handle scheduling delays, a way is to: <ul id="ul0007" list-style="none"><li id="ul0007-0001" num="0000"><ul id="ul0008" list-style="none"><li id="ul0008-0001" num="0098">Keep a history of events—a reaction to events several cycles after they happened, at precisely the cycle required. The reaction is so that there are some accumulation operations that are reset during the iteration in question, and other operations that are not.</li><li id="ul0008-0002" num="0099">Specify which operations react to the events—along the lines of, “the first two operations issued during the iteration need not be affected, but the third and the fourth are”. Specifying which operations react to the events may be performed using two registers, software-programmable stage selector register <b>508</b> and an internal, hardware-maintained history shift register <b>506</b>.</li><li id="ul0008-0003" num="0100">History shift register <b>506</b> is a 32-bit shift register updated at every cycle as follows:</li><li id="ul0008-0004" num="0101">All bits are shifted to the left losing the most significant bit (MSB), so a history of at most 32 cycles is kept.</li><li id="ul0008-0005" num="0102">The least significant bit (LSB) is set to 1 if an AGU <b>308</b> issued a load/store command that incremented the counters of the AGU <b>308</b> such that a location was reached triggering the event type configured at event selector register <b>504</b>.</li></ul></li></ul>
The behavior of an accumulator reset <b>306</b> is modified to reset accumulator <b>36</b> if an accumulation command is issued at a cycle when stage selector <b>508</b> & history shift register <b>506</b> !=0. i.e. not equal to zero, that is, when a bit is set. Stage selector <b>508</b> is thus used by software to specify the one or more number or numbers of cycles at which, after an event happens, reset should occur—in the hypothetical example of “third and fourth instructions”, 2 bits corresponding to the delay between those instructions and the AGU <b>308</b> load/store command triggering the event would be set. That is, bits 7 and 9 are set, assuming that the 3rd instruction is issued 7 cycles after the AGU <b>308</b> load/store command and the 4th instruction is issued 9 cycles after the AGU <b>308</b> command. Stage selector <b>508</b> may be configured to select several stages.
Accumulator reset is a feature further expanding the utility of multidimensional ZOLs. Also there are specific reasons for accumulator reset <b>306</b> to be more useful when compared to the average general-purpose processor or DSP accelerator. Accumulator reset is useful, very specifically, when the accumulators <b>36</b> of ALUs <b>320</b> are reset every time through very short loops. Vector processor <b>304</b> has more such cases than the average processor because of having to process narrow regions of interest and because of running deeply nested loops with very short innermost dimensions, such as loops to implement some forms of matrix multiplication and filtering.
Reference is now made to <figref idref="DRAWINGS">FIG. 6<i>a </i></figref>which shows a method <b>601</b><i>a </i>and <figref idref="DRAWINGS">FIG. 6<i>b </i></figref>which shows a method <b>601</b><i>b </i>which may be a continuation of method <b>601</b><i>a</i>, according to a feature of the present invention. In step <b>603</b> multiple events may be generated by an address generation unit (AGU) <b>308</b> and/or ZOL module <b>362</b>. The events generated by the AGU <b>308</b> and/or ZOL module <b>362</b> may be stored in memory <b>302</b> (step <b>605</b>) or passed accumulator resets <b>306</b> by event lines <b>32</b>. In step <b>607</b>, at least one of the events generated AGU <b>308</b> and/or ZOL module <b>362</b> may be selected and number of events <b>32</b> from AGU <b>308</b> and/or ZOL module <b>362</b> are input into event register <b>502</b>. The output of event register <b>502</b> is E bits which correspond with the number of events <b>32</b> which is logically ‘ANDed’ together with the K bits of event selector register <b>504</b> via AND gate <b>510</b><i>a </i>(step <b>609</b>). The K bit output <b>61</b> of AND gate <b>510</b><i>a </i>is then inputted into OR gate <b>512</b><i>b </i>(step <b>611</b>) which gives a single bit output <b>63</b> by virtue of the K bits ORed with each other. The single bit output <b>63</b> is placed into history shift register <b>506</b>. The single bit output <b>63</b> of OR gate <b>512</b><i>a </i>may then be the basis for the accumulator reset <b>34</b> shown in the previous figures.
Where the single bit output <b>63</b> of OR gate <b>512</b><i>a </i>is not the basis for the accumulator reset <b>34</b> shown in the previous figures, the N bit output of history shift register <b>506</b> is then ‘ANDed’ with the N bits of stage selector <b>508</b> via AND gate <b>510</b><i>b </i>(step <b>615</b>). The N bit output <b>65</b> of AND gate <b>510</b><i>b </i>is then input into the N bit input of OR gate <b>512</b><i>b </i>(step <b>617</b>), where the N bits are ORed with each other to give a single bit output <b>67</b>. The single bit output <b>67</b> of OR gate <b>512</b><i>b </i>may then be the basis for the accumulator reset <b>34</b> shown in the previous figures.
A simplistic implementation of steps <b>615</b> and <b>617</b> could have a constant delay (of 3 cycles for example), so there is no nee need for an AND and an OR in step <b>615</b> and <b>617</b> respectively. Rather, such an implementation would sample the event 3 times and use the oldest sample. A further simplification is not to have a history at all but rather reset the accumulator <b>36</b> immediately when the event arrives via event line <b>32</b>. An event history could be kept, for example, at the AGU <b>308</b> side which would give the same accumulator reset <b>306</b> idea shown above. The constant delay may also be applied to steps <b>609</b> and <b>611</b>.
Reference is now made to <figref idref="DRAWINGS">FIG. 7</figref> which shows a method <b>701</b>, according to a feature of the present invention. As shown previously vector processor <b>304</b> includes multiple arithmetic logic units (ALU) <b>320</b> and multiple address generators <b>308</b> which connect to multiple accumulators resets <b>306</b> via event lines <b>32</b>. In step <b>703</b> multiple image patches from image frames <b>15</b> are inputted into processor <b>304</b> via memory <b>302</b>. In step <b>705</b> a processing loop for processing the image patches may be initiated. The processing of the image patches (step <b>705</b>) may be over multidimensional zero-overhead loops (ZOLs) supervised by ZOL module <b>362</b>. Resetting accumulator <b>36</b> (step <b>707</b>), while processing the processing loop, avoids breaking pipelined execution of processor <b>304</b>. The resetting of accumulator <b>36</b> in step <b>707</b>, also avoids breaking out of the multidimensional zero-overhead loops (ZOLs).
The indefinite articles “a”, “an” is used herein, such as “an output”, “an AND gate have the meaning of “one or more” that is “one or more outputs” or “one or more AND gates”.
Although selected features of the present invention have been shown and described, it is to be understood the present invention is not limited to the described features. Instead, it is to be appreciated that changes may be made to these features without departing from the principles and spirit of the invention, the scope of which is defined by the claims and the equivalents thereof.
Contents4
8 sheets
Sheet 1 Sheet 2 Sheet 3 Sheet 4 Sheet 5 Sheet 6 Sheet 7 Sheet 8
Every citation, both ways
| Document | Relation | Office | Cited during |
|---|---|---|---|
| US2005275428A1 | Cites | United States of America | Search report |
| US2006015701A1 | Cites | United States of America | Search report |
| US2008141013A1 | Cites | United States of America | Search report |
| US2012216012A1 | Cites | United States of America | Search report |
| US2014189287A1 | Cites | United States of America | Search report |
| US2017220345A1 | Cites | United States of America | Search report |
| US5659690A | Cites | United States of America | Search report |
| US5673407A | Cites | United States of America | Search report |
| US6023759A | Cites | United States of America | Search report |
| US6151682A | Cites | United States of America | Search report |
| US6658578B1 | Cites | United States of America | Search report |
| US20050275428A1 | Cites | United States of America | Search report |
| US20060015701A1 | Cites | United States of America | Search report |
| US20080141013A1 | Cites | United States of America | Search report |
| US20120216012A1 | Cites | United States of America | Search report |
| US20140189287A1 | Cites | United States of America | Search report |
| US20170220345A1 | Cites | United States of America | Search report |
10 priority claims, no other members on record
Priority claims10
| Document | Office | Kind | Date |
|---|---|---|---|
| 201213557337 | United States of America | A | |
| 201213557337 | United States of America | A | |
| 201615002718 | United States of America | A | |
| 201615002718 | United States of America | A | |
| 201715726410 | United States of America | A | |
| 13557337 | – | – | – |
| 15002718 | – | – | – |
| US201213557337 | – | – | – |
| US201615002718 | – | – | – |
| US201715726410 | – | – | – |
34 transactions on the USPTO file
1 non-final rejection on record.
- Non-final rejections
- 1
- Final rejections
- 0
- RCEs
- 0
- Appeals
- 0
Over time
Point at a mark for the transactionTransactions
| Event | Code | |
|---|---|---|
| Date Forwarded to ExaminerFWDX | FWDX | |
| Paralegal TD Not acceptedP575 | P575 | |
| Paralegal TD Not acceptedP575 | P575 | |
| Terminal Disclaimer FiledDIST | DIST | |
| Terminal Disclaimer FiledDIST | DIST | |
| Response after Non-Final ActionA... | A... | |
| Request for Extension of Time - GrantedXT/G | XT/G | |
| Mail Post CardPST_CRD | PST_CRD | |
| Email NotificationEML_NTF | EML_NTF | |
| Mail Non-Final RejectionNon-final rejectionMCTNF | MCTNF | |
| Non-Final RejectionNon-final rejectionCTNF | CTNF | |
| Email NotificationEML_NTR | EML_NTR | |
| Application ready for PDX access by participating foreign officesCCRDY | CCRDY | |
| PG-Pub Issue NotificationPG-ISSUE | PG-ISSUE | |
| Case Docketed to Examiner in GAUDOCK | DOCK | |
| Email NotificationEML_NTR | EML_NTR | |
| Application Is Now CompleteCOMP | COMP | |
| Filing Receipt - UpdatedFLRCPT.U | FLRCPT.U | |
| Application Is Now CompleteCOMP | COMP | |
| Application Dispatched from OIPEOIPE | OIPE | |
| FITF set to NO - revise initial settingFTFI | FTFI | |
| Patent Term Adjustment - Ready for ExaminationPTA.RFE | PTA.RFE | |
| Payment of additional filing fee/PreexamFLFEE | FLFEE | |
| Electronic ReviewELC_RVW | ELC_RVW | |
| Email NotificationEML_NTF | EML_NTF | |
| Email NotificationEML_NTR | EML_NTR | |
| Notice Mailed--Application Incomplete--Filing Date AssignedINCD | INCD | |
| Filing ReceiptFLRCPT.O | FLRCPT.O | |
| Cleared by OIPE CSRL194 | L194 | |
| PTO/SB/69-Authorize EPO Access to Search ResultsSREXR141 | SREXR141 | |
| Applicants have given acceptable permission for participating foreignAPPERMS | APPERMS | |
| IFW Scan & PACR Auto Security ReviewSCAN | SCAN | |
| Entity status set to undiscounted (initial default setting or status change)BIG. | BIG. | |
| Initial Exam Team nnIEXX | IEXX |
1 legal event, as the office reported them to INPADOC
Events
| Event | Code | |
|---|---|---|
| Maintenance fee paymentMAFP | MAFP |
Numbers
- Publication
- 10255232
- Publication, DOCDB
- 10255232
- Publication, EPODOC
- US10255232
- Application
- 15726410
- Application, DOCDB
- 201715726410
- Application, EPODOC
- US201715726410
Titles
- English
- Computer architecture with a hardware accumulator reset
Patent term adjustment
- Applicant delay
- −31 days
- Net adjustment
- 0 days
Classification
- CPC, 11
- G06F15/82
- G06F9/542
- G06F9/3001
- G06F9/325
- G06F9/345
- G06F9/30029
- G06F9/3836
- G06F9/3885
- G06V20/56
- G06F11/30
- G06K9/00791
- IPC, 8
- G06F11 30
- G06F9 38
- G06F9 30
- G06F15 82
- G06F9 54
- G06K9 00
- G06F9 32
- G06F9 345
- USPC, 1
- 710307000