Hardware Support for a

Functionally-Programmed

Tagged Token Architecture

Jonas Alowersson and Glenn Jennings

Department of Computer Engineering, Lund University

P.O. Box 118, S-221 00 Lund, Sweden

Tel. (+46)-46-1097 63, Fax (+46)-46-1047 14

Electronic Mail: [email protected]

Abstract

As part of an investigation into non-dataflow data-driven tagged-token architectures, we examine the tagging mechanism of such an architecture from the execution model level down to its hardware implementation. We propose a new execution model for such a tagged-token architecture, not Petri-net based but rather exploiting a functional programming style having applicative-order evaluation. The computation's execution graph is dynamically generated according to easily understood dynamic tagging rules, and permits for conceptually unbounded parallelism for an interesting class of list-oriented computations. The major bottleneck in such an architecture is the tag-matching function which we examine in some detail. A single-chip matching unit, utilizing custom VLSI, under development is described. It will use hardware hashing to search for matches in a 2048 words dynamic memory. Simulations presently indicate that the unit will have a sustained matching rate in excess of 10 MHz. Modifications needed in the matching unit to implement the suggested execution model are discussed.

1 Introduction

This study is part of an investigation into data-driven computer architectures [Alo92] [Jen92b] [Reg87] based on a functional programming style [Bac78] as opposed to the dataflow paradigm [Den75] [AA82]. Here we distinguish functional languages, which are generally recursive in programming style (being rooted in the lambda calculus [Bar84] [Dar85]), from dataflow languages [Ack82] which, having their underlying foundations in the Petri net [Rei85] have cyclic program graphs [Den75] [GKW85] and therefore an iterative programming style [Ack82]) as well as other sequential biases, such as time-sequential ?streams? [CDP83] [Kro83] [Nit89].

An important survey of related investigations can be found in [Veg84]. The dataflow approach has dominated recent research into data-driven parallel machine architectures [GKW85] [SM82] [SY+89], while advanced architectures for functional languages have generally been based on demand-driven (?lazy,? that is, normal-order evaluation) implementations [Cur77]. But the data-driven functional programming style has the potential of exposing a tremendous amount of inherent parallelism in a broad class of vector and matrix oriented computations [Veg84], something that has only been seriously investigated for the dataflow paradigm [AA82] [CA88]. Toward data-driven architectures based on a functional programming style we will discuss a novel machine execution model [Jen92a] which is based on token tagging, especially appropriate for the execution of functional programming languages evaluated in applicative order (data-driven), together with progress made toward its most important implementational component: a high-performance matching store.

This paper is organized as follows. First, we will take a simple application (computation of a dot product) and show how a functional computation would proceed. We do this with some thought to the reader who may not be thoroughly initiated into functional programming. Second, we further examine the implications of our proposed functional language, and show how it maps onto the execution model. The mapping from the dot product program onto the proposed execution model is expected to be difficult for the reader, so we will augment these two sections with a number of intuitive arguments and figures. Here we also develop the model's relationship (especially the differences) to that of dataflow architectures. Third, we discuss the implementation of the proposed execution model and introduce the reader to matching stores in this context. Finally, we discuss our investigation into matching stores in some detail.