DDN(ID:4492/dat007)Data-Driven NetsAl Davis' experimental data-driven system for the Burroughs DDM#1 (Data-Driven Machine Number 1) developed at the niversity of Utah in 1977, but based on his PhD system SPL. Effectively a recursive assembler, based on Glushkov's principles, and influenced by the dataflow systems of Dennis and Rodriguez. (To fully understand the system in all its elegance, Davis's 1978 paper must be consulted) The machine (and to a lesser extent, the language) were designed as a proof of concept to Burroughs, while Davis was attached to the Burroush ADSC An extension of the language (GPL) ran on the DDM2, built a few years after by Burroughs and Davis Related languages
References: Introduction DDMI (Data-Driven Machine #1) was built in an attempt to investigate some ideas about the organization of machines which would be capable of supporting very high levels of concurrency, and which would also be both efficient and economical with respect to current technology. The machine language programs of DDMI are represented as Data-Driven Nets, or DDN's. DDN's are bipartite graphs consisting of cells interconnected by directed arcs. The arcs act as data paths which carry information to the cells. The cell type indicates how input information will be used to produce output information. DDN's are similar to the dataflow net representations of Dennis and Rodriguez. The advantage of DDN's with respect to these other net representations are I) that no distinction need be made between data items used for control and other data items, and 2) that the DDN schemata contains a more general selection of primitive elements. DDN's by nature are highly parallel, asynchronous, distributed control, program specifications. This implies that an efficient machine structure for evaluating DDN programs should possess similar characteristics. A recursive architecture was chosen to meet the above criteria. In defining a new set of guidelines for recursive machines and computing technology, Glushkov, et al proposed the following principles: Pl. Recursive machines contain a limitless number of levels of machine language. P2. All program elements for which operands are available are to be executed. P3. Memory structure should be flexible, P4. There should be no limit to the number of allowed machine elements. P5. These machines should have a flexible, reprogrammable structure. By recursively structured, it is meant that at any level of the architecture the structure at that level is the same as the structure at any other level. Today's LSI component technology makes modular extensible structures economically attractive. By minimizing the number of module types and allowing these types to be used repetitively in an extensible recursive structure, the resulting cost structure is attractive. Moreover if such a machine structure can fulfill the needs for machines of all sizes, support efforts may be limited to a single class of machines. Glushkov's principles do not specify how recursive machine structures are to be controlled. It is doubtful that centrally controlled parallel machines can be efficient. Performance measurements on STAR and ILLIAC IV provide good examples of this problem. Centrally controlled systems suffer the further disadvantage in that they cannot be arbitrarily extended. These problems can only be overcome by special tuning or programming for larger structures. This situation can be resolved by a new principle. P6. Modules of recursively structured machines should function in a fully distributed asynchronous manner. Fully distributed systems are defined here to have two principal characteristics: Cl) At no time can a module of a fully distributed system determine the total system state; and C2) A fully distributed system is incapable of enforcing simultaneity in its distributed modules. This results in the necessity for modules to function only on the basis of the module's own local time. The asynchronous protocol chosen for the self-timed modules of DDMI is a four-cycle requestacknowledge scheme, and is described in section III. The benefit of these self-timed modules and the recursive structure of the machine is that modules may be added without limit and no special hardware modules, tuning, or programs need be added to support arbitrarily larger structures. Extract: Characteristics of the Machine Language Characteristics of the Machine Language DDN's are cyclic, bipartite graph structures consisting of a collection of cells and a collection of directed data paths interconnecting these cells. Quantum units of information called data items travel over the data paths from one cell to another. Data items are typed, e.g. program, message, vector, scalar, etc., and are variable in length. Data paths function as FIFO storage devices when more than one data item is present. The lengths of these queues are constrained within DDMI by the availability of physical resources. There are several types of DDN cells in the actual machine language. These cell types allow such program constructs as calls, conditionals, arbitration, iteration, distribution of data items, deterministic merging, and synchronization. The semantics associated with cell types will be abstracted here by assigning a cell function to each individual cell. When a certain subset of a cell's input data paths (the firing set) each contain at least one item, that cell is said to be fireable. A cell fires at some finite, but unspecified time after it becomes fireable. This notion of a finite, but unspecified delay is essential if the schema is to fit within the functional framework of a fully distributed asynchronous environment. When a cell fires the set of items comprising the firing set are consumed, and a set of resultant data items are placed on some subset of output data paths. The values of these resultant items and the selection of data paths on which they are placed, depend upon the cell function. No assumption is made about the relation between the times at which the items appear on the output data paths or the order in which they appear. A cell is said to have fired only after all of the firing set data items have been destroyed and all output items have been placed on the desired output paths. Data items are physically implemented as distributed storage units. Implicit in this scheme is the existence of request-acknowledge communication protocols between cells, or between cells and data path FIFO stores. This locality of information guarantees that programs written as DDN's are side effect free. This distributed storage implementation and the need for destruction of data items on cell firing implies that if a particular data item is to be used concurrently in more than one place or time in the net, then that data item must be explicitly copied and sent to the multiple local domains where it will be used. As a result, any DDN cell output may be multiply copied. Al Davis at the University of Utah is acknowledged as having built the first operational hardware data-flow processor, called the Data-Driven Machine 1 (DDM1),24 in collaboration with the Burroughs Corporation in 1977. Davis also designed the DDN language25 for use on DDMl based on the language from his PhD thesis, SPL.26 DDMl was built to prove to the Burroughs Corporation that data-flow concepts were feasible. A second machine, DDM2, was built based on the same architecture as DDMl but ran 140 times faster. According to a personal communication from Davis, "This machine was much more of a real machine rather than just a quick and dirty proof of ideas (which was the case with DDMl)." This second machine was programmed in GPL. Unfortunately, there was little published on DDM2 or GPL. in Annals of the History of Computing 16(4) Winter 1994 view details |