---
title: "Architecture and Applications of DADO: A Large-Scale Parallel Computer for Artificial Intelligence"
authors:
  - "Salvatore J. Stolfo"
  - "Daniel P. Miranker"
  - "David E. Shaw"
doi: ""
url: "https://ijcai.org/proceedings/1983/205"
pdf: "https://ijcai.org/proceedings/1983/0205.pdf"
venue: "Proceedings of the Eighth International Joint Conference on Artificial Intelligence"
year: 1983
pages: "850-853"
track: "Systems Support"
keywords:
---

# Architecture and Applications of DADO: A Large-Scale Parallel Computer for Artificial Intelligence

Salvatore J. Stolfo, Daniel P. Miranker, David E. Shaw

*Proceedings of the Eighth International Joint Conference on Artificial Intelligence*, pages 850-853.

## Abstract

As part of our research on very high pe rforman ce parall el architectures, we have been inv est igating machin ea.rc hit<' ct ur cs spec ially adapted to th e highly effici e nt implementation of a rtificia l int elligence (AJ) software. In the course of our rPsear ch we d es ign ed DADO, a highly parallel , VLSI- based, t.recst ru ct. ured ma chin e, andimpl cmPnted a high-speed algo rithm for production syste ms on a simul ato r for DADO. Subsequent research has convin ced us that DADO ca n s upp o rt many other AJ applications, including the very rapid execution of PROLOG' programs, and a large s har e of the sy mbolic processing typi ca l of co ntemporary knowledge-based sys tems . In this brief re port, we outline the hardware de~ign of a. mod e rate s iz e DADO prot oty pe , comprising 1023 pr oeessing e lement s, which is c urrently underco ns tructi on at Columbia University. W e then sketch thesoft ware base being impleme nt ed on a small 15 processing clement prototype s ystem including several app li cations writt en in Pl'Ljl'vf , a high-lev el languag e d es igned for specifying para ll el co mput at ions on DADO.

## Full text

## 1. Introduction

As know ledge-based systems begin to grow in size and scope, they will begin to push conventional computing systems to their limits of operation. Even for experimental systems, many researchers reportedly experi ence frustration based on the length of time rPquired for their operation. For applications requiring real-time response from an expert. system (for example, electroni c warfare) conventional implementations may not be practical. Recently, several AI researchers (see [Nilsson Hl80], for example) have suggested that significant increases in the performance of contemporary rach cont.ammg its own processor, a small amount (2K bytes, in the current design of the full-scale version) of local rrwdom access mPmory (RAM), and a specialized 1/0 switch, which will be implemented using a custom intPgratcd circuit. The PE's are interconnected to form a complete binary tree.

*This research was supported in part by the Defense Advanced Research ProJects . Agency under contract N000:3U-82-C-O,l27 , as well as Intel Corporation, Digital Equipmrnt Corporation IBM Corporation and Valid Logic Systems. We gratefully acknowledge their support.

Within thl' DADO machine, each PE is capable of expcuting in eithrr of two mocks. In the first, which we will call SIMD mode (for single instruction stream, multiple data stream), the PE executes instructions broadcast by some ancestor PE within the tree. In the second, which will be referred to as !1-flMD mode (for multipiP instruction stream, multiple data stream), each PE exPcutPs instructions stored in its own local RAM independently of the other PE's. A ·single control processor (CP) , adjacent to the root of the DADO tree, controls the operation of the entire ensemble of PE's.

When a DADO PE enters MIMD mode, its logical state is changed in such a way as to effectively "d isconn ect" it and its descendants from all higher-level PE's in the tree. ln particular, a PE in MlMD mode does not receive any instructions that might be placed on the !reP-structured communication bus by one of its ancestors. Such a PE may, however, broadcast instructions to be executed by its own descendants, providing all of these descendants have themselves been switched to SIMD mode. The DADO machine can thus be configured in sueh a way that an arbitrary internal node in the tree arts as the root of a tree-structured SIMD device in which all PE's execute a single instruction (on different data) at a given point in time. (A PE in SIMD mode may also be instructed to disable itself, in which case instructions placed on the broadcast bus will be ignored by the PE, while descendants of the PE who rPmain enabled will receive and execute such instructions.) Thus, DADO provides direct support for large-scale MSI~1D (multiple SJMD) execution. This fl exible architectural design supports the logical division of the machine into distinct partitions, each executing a distinct task.

The DADO 1/0 switch, which will be implemented in custom VLSI and incorporated within the 1023 proeessing element version of the machine, has been dPsigned to support communication between physically adjacent tree neighbors, as well as communication between PE's that are adjacent in a logical linear ordering Pmhcdded within the tree. In addition, a specialized combinatorial circuit incorporated within the 1/0 switch will allow for the very rapid selection of a single distinguished PE from a set of candidate PE's in the tree. Currently, the IS processing element version of DADO performs these operations with the sequential logic embodied in its off-the-shelf components.

In thP following sect ions we outline the hardware dPsign of the DADO prototypes and then dPscribe

1'1'/,jAt, a variant of the PLj,H language, providing several primitives for specifying parallel computation on /).'\DO. In the concluding sections we overview the applications currently under aetive investigation for implementation on DADO.

## 3. The DADO Prototypes

A IS-element DADO prototype, constructed from (partially) donated parts supplied by Intel Corporation, is c-urrently operational. The IS PE's are int&lt;&gt;grated on two wire-wrap prototype boards supplied by Valid Logic Systems. A much larger version, DAD02, is under construction which will incorporate 1023 PE's constructed from two commercially available Intel chips. The DAD02 prototype consists of 32 printed circuit boards, each containing 32 PE's, housed in a. rack which can fit in either a DEC VAX 11/7SO cabinet, or an IBM Series I cabinet.

## 3.1. The Prototype Processing Element

Each PE in the prototype systems incorporate an Int el 8751 microcomputer chip, serving as the processor and an 8K X 8 Intel 2186 RAM chip, serving as the local nwmory. (Two simple logic gates are used to properly int8grate the RAM and processor.) Although the full­ scale version of DADO has been designed to incorporate a 21\. RAJ-.1 within each PE, an 8K RAM was chosen for the prototype PE to allow a modest degree of flexibility in designing and implementing the software base for the full version of the machine.

The Intel 87Sl is a powerful 8-bit microcomputer incorporating a 4K eraseable programmable read only memory (EPROM), and a 2S6-byte RAM on a single silicon chip. One of the key features of the 87Sl processor is its 1/0 capability. The four parallel, 8-bit ports provided in a 40 pin package has contributed substantially to the ease of implementing a binary tree interconnection between processors.

In the IS-clement prototype design, the communication primitives and execution modes of a. DADO PE are implementpd by a small kernel system rPsidcnt within each processor EPROM. The specialized 1/0 switch env isioned for DAD02 is simulated in the smaller version by a short sequential computation. Based on our estimates of minimum clock speed, DAD02 will be capable of executing in excess of 600 million instructions per second, assuming inter-processor communication to be implcnwnted with a combinational logic 1/0 switch. Alt.hough pipelined communication is employed in the kernel design, it is expected that only ISO million instructions per S(·cond would be achieved using the cu rrent d(·sign. Thus, the design and implementation of a custom I/0 chi p forms a major part of our current rest&gt;arch activitit's.

## 3.2. The PE kernel

As noted, the 4K EPROM of the Intel 8751 stores the system kernel of a PE, which includes code performing the most basic communication and synchronization functions as well as the simulation of SIMD and MIMD modes of execution. The kernel system is designed in such a way as to logically divide the 8K RAM space of the Intel 2186 chip into two portions for each of the execution modes. The initial 1K portion, referred to as SIMD RAl\I, is a reserved data space for variables and constants operated upon by a PE while in SIMD mode. The remaining 7K portion of RAM is used for storage of code, as well as the local variables used during the MIMD mode of operation.

## 4. Programming DADO

PL/M [Intel 1982] is a high-level language designed by Intel Corporation as the host programming environment for applications using the full range of Intel microcomputer and microcontroller chips. A superset of PL/M, which we call PPL/M, has been implemented as the system-level language for the DADO prototypes. PPL/M provides a set of facilities to specify operations to be performed by independent PE's in parallel.

Intel's PL/M language is a conventional block­ oriented language providing a full range of data structures and high-level statements. The following two syntactic conventions have been added to PL/AI for programming the SIMD mode of operation of D.4DO. The design of these constructs was influenced by the methods employed in specifying parallel computation in the GLYPNIR language [Lowrie et al. 1975] designed for the ILLIAC IV parallel processor. The SLICE attribute defines variables and procedures that are resident within each PE. The second addition is a syntactic construct, the DO SIMD block, which delimits PPL/M instructions broadcast to descendent SIMD PE's. (In the following definitions, optional syntactic constructs are represented within square brackets. )

The SLICE attribute:

DECLARE variable[(dimension)] type SLICE;

name: PROCEDURE[(params)] [type] SLICE;

Each declaration of a SLICEd variable will cause an allocation of space for the variable to occur within the SIMD RAM of each PE (the initial IK portion). SLICEd procedures are automatically loaded within the 7K MIMD portion of RAM (by an operating system executive resident in DADO's CP).

Within a ?PL/M program, an assignment of a value to a SLICEd variable will cause the transfer to occur within each ena.blrd SIMD PE concurrently. A constant appearing in the right hand side will be automatically broadcast to all enabled PE's. Thus, the statement

<!-- formula-not-decoded -->

where X is of type BYTE SLICE, will assign the value 5 to each occurrence of X in each enabled SIMD PE. (Thus, at times it is conven ient to think of SLICEd variables as vectors which may be operated upon, in whole or in part, in parallel.) However , statements which operate upon SLICEd variables can only be speci fi ed within the bounds of a DO SIMD block.

DO SIMD block:

DO Sll'viD; r-staternent 0 ; r-statementn; END;

The r-statc·ment is restricted to be any PL/Af statement incor-porating only SLICEd variables and cons tants.

In addition to the full range of instructions available in PPL/M, a DADO PE in MIMD mode will have available to it a set of built-in functions to perform the basic tree communication operations, in addition to functions controlling the various modes of execution. The interested reader is referred to [Stolfo et al. 1982] for the details of these primitives, as well as a complete specification of the PPL/M language.

## 5. Applications

Thus far , 12 people have written PPL/M programs for D.4DO. The applications that have been wri tten, at various stages of completion , include system-level di agnostics, numeric processing and AI applications. The largest share of our software effort , though, has concentrated on parallel implementations of various AI applieat.ions.

The most important of these is an algorithm for the parallel execution of produ~tion system programs. A restricted model of production systems has been implemented in PPL/M using this algorithm and is currently being tested .

In its simplest form, the algorithm operates in the following way:

- J. By ass igning a singlt' rule to a unique PE at a fixed level wit.hin the tree (referred to as the

PM-level), executing in MHv1D mode, each rule in the system is matched concurrently. Thus, the time to calculate the set of matching rules on each cycle is independent of the number of pmductions in the system.

2. By assigning a data item in Working Memory (WM) to a single PE below the PM-Ievel executing in SIMD mode, WM is implemented as a true hardware content-addressable memory. Thus, the time required to match a single pattern element is independent of the number of facts in WM.
3. Lastly , the selection of a single rule for execution from the conflict set is also performed in parallel. Thus, the logarithmic time lower bound of comparing and selecting a single item from a collection of items is achievable on DADO as well.

This algorithm offers a number of advantages over the highly efficient RETE match algorithm reported by Forgy, while maintaining much of its inheritently efficient capabilities. We quote from [Forgy 1982]:

... Certainly the [RETE] algorithm should not be used for all match problems; its use is indicated only if the following three conditions are satisfied.

- The patterns must be compilable [to more primitive match tests] ...
- The objects must be constant. They cannot contain variables or other non­ constants as patterns can.
- The set of objects must change relatively slowly. Since the algorithm maintains state between cycles, it is inefficient in situations where most of the data changes on each cycle.

In its current form, the DADO algorithm does not provide a means to compile patterns into primitive match tests, although it does not directly exclude this possibility. However, the ability of a DADO PE to execute code independently of other PE's permits pattern matching ~ts common to several rules to be performed in parallel, as well as a more powerful pattern match operation: unification. Thus, data items within DADO's WM may contain variables or other non-constants. (It is interesting to note that this capability forms the basis of the implementation of PROWG on DADO.) Lastly, the DADO algorithm does not restrict the amount or scope of WM modifications, but. rather permits large global changes to be made to WM very efficiently (by broadcasting such changes from the root PE). However, the DADO algorithm does not save state between cycles. H.ather, in situations in which few WM changes are made on each cycle, the DADO algorithm recomputes much of its match results caleulated on the previous cycle. We have recently discovered, though, that the basic DADO algorithm can be easily extended to directly implement this temporal redundancy .

Many problem solving tasks, though, are well suited to implementation using the RETE algorithm. Thus, we have also recently begun work on implementing the RETE match algorithm directly on DADO. It is too early in our investigations to make any precise claims about the performance of the RETE algorithm on DADO. However, since the data-flow discrimination network compiled by the RETE algorithm produces nodes with a maximum fan-in of two, it is our belief that the match network may be directly mapped onto the DADO tree structure permitting massive parallelism to be directly exploited. The comparative evaluation of the two approaches forms a major part of our current research activities.

Our plans include the completion of an interpreter for a more general vNsion of production systems in the coming months. An improved algorithm for the rapid evaluation of hierarchical produclion systems, typified by MYC/N-Iike systems, is being investigated for implementation on DADO as well.

Lastly , we note the relationship of PROLOG and DADO. Since PROLOG may be considered as a special case of production systems, it is our belief that DADO can quite naturally support performance improvements of PROLOG programs over von Neumann implementations. Some interesting work in this direction has been reported in [Taylor et al. 1983] .

By way of summary, it is our belief that DADO can in fact support the high-speed execution of a very large class of Al applications, in particular, the rapid execution of expert systems implemented in production system form. Coupled with an efficient implementation in VLSI tec-hnology , the large-scale parallelism achievable on DADO will indeed provide significant performance improvements over conventional machines at moderately low cost. Indeed, our preliminary statistics suggest that DAD02 is expected to execute Rl/XCON, the Digital Equipment Corporation VAX configuration program reported by McDermott [1981], at an average rate in excess of 150 production system cycles per second! Presently, Rl/XCON executes on a VAX 11/780, at a rate of 2 to 600 production system cycles per minute. It is interesting to note further that this larger prototype will be comparable in hardware complexity and cost to the DEC VAX 11/750, a smaller, slower and much less expensive version of the VA\_,'{ 11/780.

## 6. Conclusion and Future Research

A large part of our work continues to involve the analytical investigation of new parallel algorithms and languages for AJ applications. Several researchers are act ively investigating methods for the rapid execution of PHOLOG programs. A large share of our efforts, though, are devoted to the hardware design and implementation of a larger ex perimental dev ice. Although adequate for further development of the software base for DADO, the J 5-element system is too limited in storage capacity and processing power to demonstrate a significant performance improvement in the execution of AI systems. Thus, using the hardware design of the 15-element system, we are currently implementing DAD02, comprising 1023 processing elements. DAD02 will incorporate a c- ustom VLSI ch ip , currently being designed at Columbia University, to perform the most basic communicatnn fum·tions in combinational logic.

Our future plans include the demonst ration of the DAD02 prototype using several ex isting la rge-scale expert systems which use the production system paradigm. Digital Equipment Corporation has expressed an interest in supplying a copy of Rl/XCON for implementation on DAD02. Bell Laboratories has also expressed a willingness to supply a copy of ACE, an expert system that has been developed to perform telephone cable maintenance [Stolfo and V esonder 1982] . Other systems are being act ively sought from other sources in the a rtificial intelligence community.

## References

1. Fahlmnn, S. E., The Has/m et Iuterconnection Scheme, T ec hni cal Report 125, Departm ent of Computer Sc ience, CarnPgi<•-Mellon U niv ersity , 1979.
2. Forgy, C. L., " RETE: A Fast Algorithm for the Many Pa.ttern/Many Obj ect Pattern Match Prob lem", AI 19, 1982.
3. Hillis , D., Th e Connection Afachine, T echni cal Report, Departm ent of Computer Science, Massachussetts Institute of T echnology, 1982.
4. Intel Corporation, PL/M-51 Users's Guide for /h e 805 1 /Ja sed Developmen t System, Order Number 121966, 1982.
5. Lesser , V. and D. Corkill , " Th e application of Artificial Intelligence to cooperative di ~t ribut e d processing", In Proceedings of th e Sixth Int erna tional Joint Con ference on Artificial Int elligence, Tokyo , J apan , 1979.
6. Lowr ie, D., T. Layman, D. Dae r a nd J . 1\1. Rand al, "G IXPNIR-A Programmi ng Lan guage for nLIAC IV ', Comm. ACM, 18 3, March, 1975.
7. McDermott, J. , " Rl : The Formative Y ears", AI Afaga z•ine 2:21-29, 1981.
8. Nilsson, N., Fundam en tal Principles of Artificial /nl elligence, Tioga Press, M<'nlo Park , California, 1980.
9. Shaw , D. E., S. J . Stolfo, H. Ibrah im , B. llill yrr , G. Vv' ied erhold and J. A. Andrews, "The NON-VON Data bas<' Machine: A Drief Overvi(•w", Databa se 8ngincering 4(2), 1981.
10. Stolfo, S. J ., D. Mir ank er and D. E. Shaw , Programming th e DADO .Hachine: An Introduction to PPL/A f, T e<-hni cal Report, D <'partrn E> nt of Comp uter Sc ience, Co lumbia U niversity, 1982.
11. Stolfo, S. J. a nd D. E. Shaw, " DADO : A Tree-structured Machine Architecture for Prod uctio n Systems", In Proceedings National Conference on Artificial Int elligence, Cn rn <'g ie-Mellon University and University of Pittsb urgh , August, 1982.
12. Stolfo, S. J. and G. T. Vesoncler, ACE: An Expert Sys tem Supporting Analysis and Afunagemen t Decision Afaking, T ec hni<-a l R eport, Depart ment of Computer Science, Columbia University, 1982.
13. Taylor, S., C. Maio,S. J . Stolfo and D. E. Shaw, PHOIDG on the DADO Afachine: A Parallel System for lligh-S'peed Logic Programming, T echnical Report, Departm ent of Computer Science, Columbia. University , 1983.