{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/69329"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/69329","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Blast: A Machine Architecture for High-Speed List Processing Using Associative Tables (Traversal, Pointers)","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.","abstract_html":"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.","abstract_has_math":false,"creators":["Sohi, Gurindar Singh"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Electrical Engineering","degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014-12-15T19:05:06Z","date_published":"2014-12-15T19:05:06Z","updated_at":"2026-07-22T22:26:00Z","subjects":["Computer Science"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["(UMI)AAI8600317"],"render_values":[{"text":"(UMI)AAI8600317","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/69329","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Sohi, Gurindar Singh"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2014-12-15T19:05:06Z","10000-01-01","1985"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Computer Science"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/69329","(UMI)AAI8600317"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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.","Made available in DSpace on 2014-12-15T19:05:06Z (GMT). No. of bitstreams: 1 8600317.pdf: 6058669 bytes, checksum: c41d8566d4be6d49df87d8b5f2e30ac3 (MD5) Previous issue date: 1985","Embargo set by: Seth Robbins for item 69495 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","U of I Only","161 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1985."]},{"key":"dc:title","label":"Title","values":["Blast: A Machine Architecture for High-Speed List Processing Using Associative Tables (Traversal, Pointers)"]}]}],"canonical_facts":{"dc:creator":["Sohi, Gurindar Singh"],"dc:date":["2014-12-15T19:05:06Z","10000-01-01","1985"],"dc:description":["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.","Made available in DSpace on 2014-12-15T19:05:06Z (GMT). No. of bitstreams: 1 8600317.pdf: 6058669 bytes, checksum: c41d8566d4be6d49df87d8b5f2e30ac3 (MD5) Previous issue date: 1985","Embargo set by: Seth Robbins for item 69495 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","U of I Only","161 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1985."],"dc:identifier":["http://hdl.handle.net/2142/69329","(UMI)AAI8600317"],"dc:subject":["Computer Science"],"dc:title":["Blast: A Machine Architecture for High-Speed List Processing Using Associative Tables (Traversal, Pointers)"],"dc:type":["text"],"thesis:degree_discipline":["Electrical Engineering"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:26:00Z"}