Electrical computers and digital data processing systems: input/ – Intrasystem connection
Reexamination Certificate
1997-10-17
2002-03-19
Dharia, Rupal (Department: 2181)
Electrical computers and digital data processing systems: input/
Intrasystem connection
C710S108000, C712S200000, C712S219000, C370S351000
Reexamination Certificate
active
06360288
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates generally to pipeline data processing systems, and more particularly, to asynchronous pipeline systems. Simple asynchronous pipelines are known, see, for example, U.S. Pat. No. 4,837,740, “Asynchronous First-In-First-Out Register Structure”; U.S. Pat. No. 4,679,213, “Asynchronous Queue System”; U.S. Pat. No. 5,187,800, “Asynchronous Pipelined Data Processing System”; and R. F. Sproull, I. E. Sutherland, and C. E. Molnar,
Counterflow Pipeline Processor Architecture
, Sun Microsystems Laboratories Publication No. SMLI TR-94-25, April 1994.
Complex pipelines are also possible. Such pipelines may branch and rejoin in many ways, or even be arranged in multi-dimensional structures. Data flowing through them may meet and interact with data items that precede or follow in sequence, or with data items flowing in a separate pipeline. For an example of a multi-issue pipelined processor, see U.S. patent application Ser. No. 08/853,970, filed May 9, 1997, and entitled “Multi-Issue/Plural Counterflow Pipeline Processor.”
It has proven difficult to design complex asynchronous pipeline systems. The difficulty comes not only from their complex arrangements of circuits, but also from their complex behavior. One might deal with the circuit complexity alone; in other fields designers deal with circuits at least as complex. In an asynchronous system, however, any signal may occur at any time, constrained only by the explicit limitations placed on it by particular circuits. There is no arbitrary “timekeeper” or “clock” by which to measure circuit performance. Rather, the designer must account for all the possible sequences of behavior that may occur, assuring that no such sequence can cause a fault. Of course, this can be difficult.
The present invention provides techniques for the design of such asynchronous systems. The design is embodied, in part, as a set of modules which are rich enough to encompass a large range of systems, but simple enough to enable relatively easy use in design. The modules described herein are generic in the sense that they provide for a variety of a practical implementations, including combinatorial logic components, data pathways of desired width, and many different interfaces. Selection of “working sets” of modules is straightforward using known methods. Furthermore, each module is asynchronous. Each module starts the task for which it has been designed when instructed to do so by an adjacent module, and each module gives completion signals to adjacent modules to coordinate their actions. The modules fit together to form pipeline systems which provide particular utility in signal processors and general purpose microprocessors.
While one could assemble, with known Macromodules such as described in W. A. Clark, and C. E. Molnar, “Macromodular Computer Systems,”
Computers in Biomedical Research
Vol. IV, Chap. 3, Academic Press, New York (1974), many different pipeline systems, systems designed with prior art modules are intrinsically slower. In addition, the large number of macromodules of prior art provided many more opportunities for implementation error. The present invention provides a set of modules adapted to assembling the most useful forms of a pipeline system. Compared to the macromodules, the present invention provides simplicity of design and ease of understanding, yet does not unduly limit the range of systems that can be assembled.
One project which employed modules for the design of processors is the TANGRAM design system. This system was developed in the Netherlands in the late 1980s and early 1990s. See, for example, Kaes van Berkel,
TANGRAM; Asynchronous Architecture for VLSI Programming,
Cambridge University Press (1993). TANGRAM modules directly implement the syntactic primitives appearing in statements written in the TANGRAM programming language for describing asynchronous systems. As with other modular structures, systems designed using the TANGRAM modules are considerably slower than desired.
The routing of data from a source pathway to selectable alternative output pathways according to data values found in the source pathway has been employed in prior art systems. One system which used this self-routing of data appears in the processor-to-memory switch of the BBN Monarch Multi-Computer. See, for example, Randall D. Rettberg, et al., “The Monarch Parallel Processor Hardware Design,”
Computer
(April 1990), pp. 18-30. In the BBN system, address bits within packets control the routing of the entire packet containing those bits. Successive address bits control the routing at successive routing stages.
Another alternative pathway routing scheme was developed for the Mosaic system, see Charles L. Seitz, et al., “The Design of the CalTech Mosaic C Multicomputer,”
Research on Integrated Systems; Proceedings
1993
Symposium,
MIT Press (1993), pp. 1-22. The Mosaic system differs from the BBN system in that although the routing information is contained within the packets themselves, it is encoded relative to the location of the switch node, rather than as an absolute destination address. In the Mosaic system each node increments the encoded information as it passes through. Only when the encoded value has achieved a certain net value is the entire packet switched to the alternate pathway. Neither the BBN Monarch system, nor the Mosaic system, used the principle of controlling data routing in one pipeline by control bits carried in another pipeline.
SUMMARY OF THE INVENTION
There are several aspects to the present invention. A first aspect deals with control of the flow of data in one pipeline system on the basis of control information flowing in another pipeline system. It is often important to modulate the flow of data items in a pipeline. For example, one may wish to eliminate certain data items from the stream flowing through a pipeline according to their values. Alternatively, one may wish to steer certain data items into one branch of a pipeline system and other data items into another branch, again according to their values. For example, one may wish to process positive numbers in one branch and negative numbers in another branch. Prior pipeline systems have been able to eliminate or steer values in a pipeline according to information traveling within the pipeline itself, as in the Monarch and Mosaic systems. The present invention provides an additional capability to enable control of the flow of data items in one pipeline according to the values of control elements in another pipeline. As will be described, in embodiments of the invention, both the pipeline being controlled as well as the pipeline providing the control are asynchronous pipelines in the sense that events and operations occur in the pipelines whenever they are ready, not in accordance with externally supplied clock signals.
In one embodiment according to our invention, a system includes a first composition of places and paths to form a first pipeline having information flowing therethrough, and a second composition of places and paths to form a second pipeline also having information flowing therethrough. The terms “Places” and “Paths” have a special meaning as will be described below. The second pipeline has at least one place with a special connection to at least one place in the first pipeline. In such a system the information flowing through the first pipeline is used to control the disposition of information flowing through the second pipeline.
A second aspect of the present invention involves the control of data latches in the primary data paths of an asynchronous pipeline. It has been common practice to include the latch control circuits inside the asynchronous control loop of each stage of the pipeline. See, e.g., I. E. Sutherland, “Micropipelines,”
Communications of the ACM
(June 1989). A system with latch control circuits inside the asynchronous control loop follows a known “bundled data convention.” According to the bundled data convention a “bundle” consisting of data signals and a validating event signal, often c
Coates William S.
Molnar Charles E.
Molnar Danna A.
Sproull Robert F.
Sutherland Ivan E.
Dharia Rupal
Molnar Danna A.
Sun Microsystems Inc.
Townsend and Townsend / and Crew LLP
LandOfFree
Method and modules for control of pipelines carrying data... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and modules for control of pipelines carrying data..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and modules for control of pipelines carrying data... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2886698