Reducing list access time for LISP execution

Prefetching items into cache can either increase or decrease memory access time, depending on how well the prefetching algorithm matches the memory reference pattern. A popular prefetching algorithm is one block lookahead (OBL). Caches help to improve system performance mainly because of the localities that exist in most program executions. The locality characteristics of list reference patterns are: both car and cdr pointer distances are likely to be small, pointers can point in either the forward or backward direction, linearization often shortens these distances, and cdr encoding is an efficient way to represent lists. Two algorithms, called two-way reflection prefetch (TRP) and forward one-block-lookahead and backward reflection prefetch (FOBRP), are designed to reduce list access time due to cache misses by taking advantage of these characteristics.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Date dc:date

10000-01-01

Author dc:creator

• Sung, Shu-Hui Helen

Contributors dc:contributor

• Davidson, Edward S.

• Computer Science

Statement dc:rights

• Copyright 1989 Sung, Shu-Hui Helen

Language dc:language

eng

Identifier

AAI8916312
(UMI)AAI8916312

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/22640