{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/22640"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/22640","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Reducing list access time for LISP execution","abstract":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Sung, Shu-Hui Helen"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Davidson, Edward S."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":null,"date_issued":"10000-01-01","date_published":"10000-01-01","updated_at":"2026-07-22T22:25:20Z","subjects":["Computer Science"],"languages":["eng"],"rights":["Copyright 1989 Sung, Shu-Hui Helen"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI8916312","(UMI)AAI8916312"],"render_values":[{"text":"AAI8916312","href":null,"code":true},{"text":"(UMI)AAI8916312","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/22640","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Davidson, Edward S."]},{"key":"dc:creator","label":"Author","values":["Sung, Shu-Hui Helen"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["10000-01-01","2011-05-07T13:46:26Z","1989"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"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":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 1989 Sung, Shu-Hui Helen"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI8916312","(UMI)AAI8916312","http://hdl.handle.net/2142/22640"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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.","Prefetching algorithms have usually been evaluated and selected according to the cache miss ratio and bus transfer ratio achieved. However, bus contention is one issue that is not properly reflected by miss ratio and transfer ratio alone. Thus, a timing model is designed and used to provide information in terms of time elapsed for accessing. This model estimates individual delay components, miss delay, contention delay, load-through completion wait, and prefetching completion wait, so that situations concerning bus contentions can be appropriately analyzed. The timing model determines the efficiency of a prefetching algorithm by its effective access time and its individual delay components, as well as its miss ratio and transfer ratio.","The performance of the proposed prefetching algorithms are evaluated by running several Lisp benchmarks, both with and without linearization, on a Lisp interpreter, and their memory traces are recorded. These traces are then fed to the timing model to evaluate the effectiveness of the proposed algorithms. Timing simulation shows: (1) increasing cache size is the best way to achieve better performance when cache size is small, (2) TRP is the best prefetching algorithm for all data accessing if a moderate size cache is provided, (3) FOBRP is the best prefetching algorithm for list prefetching, and (4) judicious application of linearization enhances the performance regardless of whether prefetching is used.","Made available in DSpace on 2011-05-07T13:46:26Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 8916312.pdf: 4818164 bytes, checksum: 2232c6e6639f8f761ac943240639ab33 (MD5) Previous issue date: 1989","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:59:00Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:27:47-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission","ETDs are only available to UIUC Users without author permission","U of I Only"]},{"key":"dc:title","label":"Title","values":["Reducing list access time for LISP execution"]}]}],"canonical_facts":{"dc:contributor":["Davidson, Edward S."],"dc:creator":["Sung, Shu-Hui Helen"],"dc:date":["10000-01-01","2011-05-07T13:46:26Z","1989"],"dc:description":["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.","Prefetching algorithms have usually been evaluated and selected according to the cache miss ratio and bus transfer ratio achieved. However, bus contention is one issue that is not properly reflected by miss ratio and transfer ratio alone. Thus, a timing model is designed and used to provide information in terms of time elapsed for accessing. This model estimates individual delay components, miss delay, contention delay, load-through completion wait, and prefetching completion wait, so that situations concerning bus contentions can be appropriately analyzed. The timing model determines the efficiency of a prefetching algorithm by its effective access time and its individual delay components, as well as its miss ratio and transfer ratio.","The performance of the proposed prefetching algorithms are evaluated by running several Lisp benchmarks, both with and without linearization, on a Lisp interpreter, and their memory traces are recorded. These traces are then fed to the timing model to evaluate the effectiveness of the proposed algorithms. Timing simulation shows: (1) increasing cache size is the best way to achieve better performance when cache size is small, (2) TRP is the best prefetching algorithm for all data accessing if a moderate size cache is provided, (3) FOBRP is the best prefetching algorithm for list prefetching, and (4) judicious application of linearization enhances the performance regardless of whether prefetching is used.","Made available in DSpace on 2011-05-07T13:46:26Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 8916312.pdf: 4818164 bytes, checksum: 2232c6e6639f8f761ac943240639ab33 (MD5) Previous issue date: 1989","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:59:00Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:27:47-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission","ETDs are only available to UIUC Users without author permission","U of I Only"],"dc:identifier":["AAI8916312","(UMI)AAI8916312","http://hdl.handle.net/2142/22640"],"dc:language":["eng"],"dc:rights":["Copyright 1989 Sung, Shu-Hui Helen"],"dc:subject":["Computer Science"],"dc:title":["Reducing list access time for LISP execution"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:20Z"}