An overview of Data-driven machine #1, Alan L. Davis, Burroughs ASD report, July 1976. DDM1 was completed at Burroughs ASD in March 1976. Basic principles. * It directly executes data-driven nets (DDN.) * Performance was sacrificed in favor of functional flexibility. DDM1 was a testbed for data-driven computing algorithms. * It uses the Barton Storage Model (SM) to represent programs and data. * DDM1 is an atomic module for use in a larger recursive machine architecture. A "module" is a processor and its associated store. An "atomic" module does not have any further substructure. * The machine is fully self-timed. Block diagram. ------------------ Input queue (IQ) <----------- External | V Atomic ------------> Output queue (OQ) ----------> External Processor (AP) <--------------- | | | | --------------> Agenda queue (AQ) | | ---- Atomic Storage Unit (ASU) Operation. * The modules intercommunicate via "messages." * A DDN to be executed arrives as a message via the IQ and is loaded into the ASU. * Data items which cause cells to become fireable also arrive as messages via the IQ. * When a data item arrives, it has two fields: the destination and the value of the item. The AP interprets the destination which is a cell in the net and finds that cell in the ASU. If the incoming data item does not make the receiving cell fireable, then the item is stored in the appropriate place in the receiving cell. * If the cell becomes fireable, then it is fired immediately using the data item on the IQ as it needs it. This scheme avoids a needless store operation on an object which will be retrieved immediately anyway. * The AP produces a result with two fields: the destination of the result message and its value. If the receiving cell is in the ASU, it is sent to the AQ. Otherwise, the result message is placed on the OQ. * Eventually, the processor turns its attention to the AQ. AQ messages are processed in the same way as IQ messages. When the AQ is empty, the processor looks for additional input from the IQ. * The "AQ before IQ" strategy means "Do as much as possible locally before accepting work from the external environment." The store. * The ASU uses the Barton Storage Model. DDM1 uses 16 characters: + The decimal digits. + "(" and ")" + "," which is equivalent to ")(" + "-" + "." + And a special character for marking purposes. * The ASU is a file system for this storage model with the commands: + Initialize. + Skip. Cursor skips over the field currently under the cursor. + Insert. Inserts the character or file before the character or file pointed to by the cursor. + Delete. Deletes the character or file indicated by the cursor. + Assign. Assigns a character or a file to the character or file indicated by the cursor. + Read. Reads the character or file pointed to by the cursor. + Head. Positions the cursor to the leading "(" of the parent field of the character currently under the cursor. + Shift. Increment the cursor. + AIndex (absolute index.) Does indexing operations starting at the first character in the store. + RIndex (relative index.) Does indexing operations starting at the current cursor position. * The ASU is a 4K by 4 bit character store using RAM chips. * A 4 cycle self-timed signaling convention controls the inputs to and outputs from the ASU. A "mapping unit," sometimes called "the mapper," is used to speed-up indexing operations. The mapper. The processor (AP.) * The processor interprets four types of cells: + Operator. + Synch. + Gate. + Distribute. * Monadic operators. + Negate. + Absolute value. + Boolean not. + Level: 0 = record, 1 = file. + Up level: Remove outside parentheses. + Down level: Add outside parentheses. + Size: Count the number of items in a file. * Dyadic operators. + Add. + Subtract. + Maximum. + Minimum. + Multiply by 10**N. + Catenate. + Decatenate. + Indexed read. + Equals. + Not equals. + Less than. + Less than or equals. + Greater than. + Greater than or equals. * Triadic operators. + Indexed write. * DDM1 operates on sign magnitude decimal integers. The absence of a sign indicates a positive integer. Integers may be of arbitrary length. All data transmissions are performed character-serial. Numbers are transmitted low-order digit first followed by the sign. A special "function unit" performs the arithmetic operations. Two special buffer stores (512 character capacity) are provided for general data storage. Retrospective. * DDM1 had a lot of internal concurrency since much of it was partitioned into special, independent machines. * Internal state is impossible to save and restore. * Vectors processing (a la APL) could not be done due to the way arithmetic was done. * Local origins (for indexing) should be added to the ASU. * Field, rather than character, transfers should be performed. * A sign trailing the high order digit implies digit alignment. However, it prevents vector processing and increases the complexity of the arithmetic hardware. *********************************************** The architecture of DDM1: A recursively structured data driven machine, Alan L. Davis, Department of Computer Science, University of Utah, Technical Report UUCS-77-113, October, 1977. Based on the 5 principles of Glushkov et al. Davis adjusts the intent of a recursive machine to mean: "that at any level of the architecture, the structure at that level is the same as the structure at any other level." One kind of organization that satisfies this criterion is a tree structured machine. Centrally controller parallel machines cannot be arbitrarily extended due to electrical problems such as clock skew. Davis adds a 6th principle: "Modules of recursively structured machines should function in a fully distributed asynchronous manner." Fully distributed systems have two principal characteristics: "1. At no time can a module of a fully distributed system determine the total system state. 2. A fully distributed system is incapable of enforcing simultaneity in its distributed modules." DDM1 does not support the notion of global state and uses self-timed modules for asynchronous control. DDM1 attempts to put many OS functions into hardware. Resource allocation is performed automatically and dynamically. It depends on exploitable concurrency and the availability of resources. Data-driven nets (DDN) * Cyclic bipartite graph structures. * Consist of "cells" and directed "data paths" (sometimes called "arcs") interconnecting the cells. * "Data items" travel over the data paths between the cells. Data items are typed and can be anything such as a program, message, vector, scalar, etc. and are variable in length. * The data paths function as FIFO queues. * Kinds of cells: + Call + Selection + Synchronization + Arbitration + Iteration (gate) + Operator + Distribution * Every cell has a set of inputs called its "firing set." When the firing set is satisfied (by the presence of tokens at the inputs which are the firing set) the cell becomes "fireable" or executable. It will "fire" (execute) some finite time after the cell becomes fireable. When a cell fires, the items at the inputs comprising the firing set are removed and resultant data items are placed on the outputs. * Two properties hold for DDNs: "1. Data items are persistent. 2. The FIFO data paths guarantee that the order of the items in any path cannot change." These are necessary (but not sufficient) conditions for deterministic functional behavior. * A data driven process (DDP) begins with a single cell and ends with a single cell. A DDP is essentially a substitution rule. * DDNs are stored as variable length, well-nested, parenthesized strings (e.g., in the form of the Barton storage model.) *********************************************** Data-driven nets: A maximally concurrent, procedural, parallel process representation for distributed control systems, Alan L. Davis, Department of Computer Science, University of Utah, Technical Report UUCS-78-108, 1978. A data-driven machine architecture suitable for VLSI implementation, Alan L. Davis, Proc. of the 1st Caltech Conference on VLSI, January, 1979, pg. 479-494. Stored state asynchronous sequential circuits, Alan B. Hayes, Department of Computer Science, University of Utah, Technical Report UUCS-80-105, May 1980. Dataflow computers: A tutorial and survey, Alan L. Davis and Paul J. Drongowski, Department of Computer Science, University of Utah, Technical Report UUCS-80-109, July, 1980.