fpst@hubcap.clemson.edu (Steve Stevenson-Moderator) (07/29/88)
[ There has been a discussion on the architecture net about paging and virtual memory in scientific programming systems. These refererences may be germane to this group. -- steve ] > [ Debate: to VM or not VM on scientific computing ] > scheme ... Most of Smith's work is in the context of prefetching cache lines from main memory and in prefetching blocks in disk files, and less on the subject of prepaging in memory hierarchies. Kishor Trivedi did a lot of work on prepaging in VM for scientific computing (array processing programs) a while back. Here are some relevant references (in BibTex format) including the one I believe you refer to above. Comments are strictly from my view. @ARTICLE{trivedi:prepage, AUTHOR = "K.S. Trivedi", TITLE = "Prepaging and applications to array algorithms", JOURNAL = ieeetc, YEAR = "1976", VOLUME = "C-25", NUMBER = "9", PAGES = "915-921", MONTH = sep, comments = "Virtual memory environment. Data space only. Gives prepaging algorithm that is optimal {\em wrt} page faults (not practical). Then gives practical modifications for any replacement algorithm that should be good. Essentially, algorithm is told when a page is dead and what pages to prefetch; dead pages are filled with demanded or prefetched pages; on page fault all spaces are filled with prefetched pages, or until no more to prefetch. So some demand fetches take long but there are fewer faults." } @article{trivedi:prepage-auto, author = {Kishor S. Trivedi}, title = {On the Paging Performance of Array Algorithms}, journal = {IEEE Transactions on Computers}, year = {October 1977}, number = {10}, pages = {938--947}, volume = {C-26}, comments = "See trivedi: prepage. Can rewrite programs to increase locality of data reference. Can add FREE and PRE calls to to demand prepaging. Maybe automated by compiler." } @article{trivedi:analysis, author = "Kishor S. Trivedi", title = "An Analysis of Prepaging", journal = "Computing", volume = 22, number = 3, year = 1979, pages = "191--210", comments = "(Also Duke TR CS-1977-7.1, but that is missing figures.) Attempts to reduce page faults at times of transition between phases of program execution, without dramatically increasing number of page fetches. Based on LRU, he compares OBL with his FDPLRU, which uses FREE(x) and PRE(x) clues about array data pages from the compiler as prefetching hints. FDPLRU is better than both over a variety of page sizes, best for small page sizes. Also shows better space-time memory product and better throughput." } @article {smith:mem-prefetch, author = "Alan Jay Smith", title = "Sequential Program Prefetching in Memory Heirarchies", journal = ieeecomp, year = 1978, month = dec, pages = "7--21", comments = "Examines general issue of prefetching at both cache and VM level for a variety of page sizes. Found it to be useful for small page sizes (like 32 bytes). No surprise since the scope of sequentiality in programs (access to instructions and data) is only about this size. Best to prefetch always rather than just at faults, and for all accesses, not just data or just instructions. Treat it like a regular page for replacement. Implementation important - avoid conflicts with normal cache use. Problem of referencing something that is still coming in was found not to be too significant." } David Kotz Department of Computer Science, Duke University, Durham, NC 27706 ARPA: dfk@cs.duke.edu CSNET: dfk@duke UUCP: decvax!duke!dfk