Files in this item

FilesDescriptionFormat

application/pdf

application/pdf8600317.pdf (6MB)Restricted to U of Illinois
(no description provided)PDF

Description

Title:Blast: A Machine Architecture for High-Speed List Processing Using Associative Tables (Traversal, Pointers)
Author(s):Sohi, Gurindar Singh
Department / Program:Electrical Engineering
Discipline:Electrical Engineering
Degree Granting Institution:University of Illinois at Urbana-Champaign
Degree:Ph.D.
Genre:Dissertation
Subject(s):Computer Science
Abstract:Due to the increasing popularity of nonnumeric processing languages such as LISP, there has been an increasing demand for machine architectures which are ideally suited to run such languages. Access to the main data structure used in LISP systems, i.e., list structures, is not conducive to a pipelined machine organization. In this thesis, we present the BLAST machine architecture for the efficient execution of LISP and other list processing languages similar to LISP.
The main feature of the BLAST architecture is the way in which lists are represented. First, we discuss our representation of lists in a logical space and their mapping onto Exception Tables (ETs). This ET representation for lists has the potential to achieve a substantial reduction in the memory space required to represent the list structure over conventional representations.
Second, we discuss the actual BLAST machine architecture and some major traversal algorithms. A CAM that has the capability of handling multiple requests simultaneously is crucial to the efficient execution of such algorithms in a pipelined fashion on BLAST.
Then we discuss some of the major tasks that are carried out in a list processing environment and see how they could be executed efficiently on BLAST. We discuss the tasks of garbage collection, elimination of redundant forwarding pointers, list copying, input and output, expression evaluation, pattern matching and construction of a cons tree. We see how LISP algorithms that require the value of leaf nodes can be modified to execute much more efficiently in BLAST.
Last, we carry out an evaluation of the BLAST architecture and discuss the various tradeoffs based on measurements of LISP program behavior carried out by previous researchers. The most important parameter influencing the performance of the architecture, the frequency of forwarding pointers, is discussed. We conclude that forwarding pointers will not occur often in BLAST, and therefore its performance will not be degraded to an intolerable extent. The various tradeoffs and the values of the tradeoff parameters that will occur in the actual dsign and physical implementation are discussed.
Issue Date:1985
Type:Text
Description:161 p.
Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1985.
URI:http://hdl.handle.net/2142/69329
Other Identifier(s):(UMI)AAI8600317
Date Available in IDEALS:2014-12-15
Date Deposited:1985


This item appears in the following Collection(s)

Item Statistics