Improving the Throughput of Pipelines with Delays and Buffers.
Abstract
A pipeline as defined here is a collection of segments of hardware which can operate simultaneously. A task flows synchronously from segment to segment for its execution. Each task follows one of several distinct task flow patterns which are assumed to be fixed and known in advance. It is characteristic of pipelines that a task can be initiated in the pipeline before an earlier initiated task has completed its execution. A problem arises when two or more tasks try to use the same segment at the same time, causing a collision. Such collisions can be avoided by appropriate scheduling of tasks and/or modification of the pipeline; or the collisions can be resolved at the time and place they occur. These alternatives are studied in this work with the objective that the throughput, i.e., average number of tasks processed per unit time, be maximized while providing considerable flexibility in scheduling of tasks. Collision characteristics of task schedules and pipelines are studied. A methodology for inserting fixed delays in a pipeline to achieve desired collision characteristics is presented.
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 01, 1976
- Accession Number
- ADA038338
Entities
People
- Janek H. Patel
Organizations
- University of Illinois Urbana–Champaign