denis@gec-rl-hrc.co.uk (Denis Howe) (03/19/90)
Mr. Qiangyi Luo asked about distributed AI on transputers and I thought this would be a good excuse to tell you about what we are doing in this area. GEC Hirst Research Centre in Wembley, UK has been involved in a project under the European Strategic Programme for Research in Information Technology (ESPRIT) in this area since 1986. The project is called PADMAVATI which stands for "Parallel Associative Development Machine as a Vehicle for Artificial Intelligence" and is developing a parallel computer with associative memory which will execute LISP, PROLOG and C. This machine will allow development of applications programs in these languages and support research into parallel architectures and languages. The project is partly funded by the European Commission and the other partners are Thomson in France and FIRST International in Greece. PADMAVATI will initially have 16 T800 transputers, each with eight megabytes of 200 ns parity checked RAM (expandable up to 16 megabytes). The transputer board we have developed (PARAPET - Parallel Processing Element) has an external memory interface for connecting off-board memory-mapped hardware to the transputer. PARAPET also has a fifth, "control" link via which the transputer can be reset, analysed and interrupted. This allows the control topology to be reconfigured in the same way as communications. Inmos standard control signals are also supported. [211zA dynamic network chip (DYNET) is being developed which allows any transputer to send messages to any other. Rather than being statically configured like Inmos's C004, DYNET uses an address tag at the start of each message to route data, possibly through several stages, to its destination. A content addressable memory (CAM) chip has also been produced in PADMAVATI. This supports associative SIMD parallelism, complementing the transputer's MIMD parallelism. Words of CAM are selected by matching against a key word supplied by the user. This key can contain "don't care" bits which will match any stored value. All words perform this matching in parallel, giving a large speed-up relative to a sequential search through RAM. Words which match can then take part in subsequent operations such as "read first" or "write all". Sequences of reads, writes and searches can be constructed to perform more complex operations such as parallel (vector) addition or relational database operations. Thus the CAM can be viewed either as an intelligent memory or as a massively parallel processor, depending on the application. PADMAVATI's CAM system consists of 72 cascaded CAM chips connected to each transputer's external memory bus. The CAM chip is a fully-custom CMOS VLSI IC, designed within the project, containing 148 words of 36 bits of storage plus processing. Interesting features include the ability to store don't care values and to store and match entries longer than a single word. The PADMAVATI CAM will be one of the largest fully parallel CAM systems to be built (700 k bytes). Applications are developed as a set of sequential processes which communicate by message passing. A kernel on each node handles message routing and memory allocation. Messages are sent to named ports. Port names are mapped at run-time by a name server to (node, address) pairs. This scheme allows efficient access to ports which can be created and placed dynamically. PADMAVATI is connected via an Inmos link to a link adaptor on the VME bus of a Sun 3/260 host which provides I/O. INRIA's LeLisp system has been ported to the transputer in the project. This will be extended with message passing primitives to allow parallel Lisp programs to be developed. Several Prolog interpreters and compilers have also been produced. Lisp and Prolog will be the main applications languages with C and transputer assembler being used for system code (no Occam!). A compiler for a functional language, written in another ESPRIT project (415), produces transputer code which runs on PADMAVATI. As a sample application, a speech understanding system from yet another ESPRIT project (954 - IKAROS) is being parallelised to run on PADMAVATI. Use of the CAM to accelerate lexical retrieval has been studied.