Blast: A Machine Architecture for High-Speed List Processing Using Associative Tables (Traversal, Pointers)
Sohi, Gurindar Singh
This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.
Permalink
https://hdl.handle.net/2142/69329
Description
Title
Blast: A Machine Architecture for High-Speed List Processing Using Associative Tables (Traversal, Pointers)
Author(s)
Sohi, Gurindar Singh
Issue Date
1985
Department of Study
Electrical Engineering
Discipline
Electrical Engineering
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(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.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
