Pipeline (computing): Difference between revisions

Content deleted Content added
WikiCleanerBot (talk | contribs)
m v2.04b - Bot T20 CW#61 - Fix errors for CW project (Reference before punctuation)
Line 22:
 
===Buffering===
Under ideal circumstances, if all processing elements are synchronized and take the same amount of time to process, then each item can be received by each element just as it is released by the previous one, in a single [[clock (computing)|clock]] cycle. That way, the items will flow through the pipeline at a constant speed, like waves in a water channel. In such "wave pipelines",<ref>{{cite web |author1=O. Hauck |author2=Sorin A. Huss |author3=M. Garg |title=Two-phase asynchronous wave-pipelines and their application to a 2D-DCT |url=https://www.semanticscholar.org/paper/Two-phase-asynchronous-wave-pipelines-and-their-to-Hauck-Garg/f5a5ba3d7da95975c97971221918fd5977ca4a90 |website=semantic scholar |access-date=14 September 2019}}</ref> no synchronization or buffering is needed between the stages, besides the storage needed for the data items.
 
More generally, buffering between the pipeline stages is necessary when the processing times are irregular, or when items may be created or destroyed along the pipeline. For example, in a graphics pipeline that processes triangles to be rendered on the screen, an element that checks the visibility of each triangle may discard the triangle if it is invisible, or may output two or more triangular pieces of the element if they are partly hidden. Buffering is also needed to accommodate irregularities in the rates at which the application feeds items to the first stage and consumes the output of the last one.
 
The buffer between two stages may be simply a [[hardware register]] with suitable synchronization and signalling logic between the two stages. When a stage A stores a data item in the register, it sends a "data available" signal to the next stage B. Once B has used that data, it responds with a "data received" signal to A. Stage A halts, waiting for this signal, before storing the next data item into the register. Stage B halts, waiting for the "data available" signal, if it is ready to process the next item but stage A has not provided it yet.
 
If the processing times of an element are variable, the whole pipeline may often have to stop, waiting for that element and all the previous ones to consume the items in their input buffers. The frequency of such [[pipeline stall]]s can be reduced by providing space for more than one item in the input buffer of that stage. Such a multiple-item buffer is usually implemented as a [[FIFO (computing and electronics)|first-in, first-out queue]]. The upstream stage may still have to be halted when the queue gets full, but the frequency of those events will decrease as more buffer slots are provided. [[QueuingQueueing theory]] can tell the number of buffer slots needed, depending on the variability of the processing times and on the desired performance.
 
===Nonlinear pipelines===