A Hierarchy of Memory for Parallel Functional Programming

点击翻译按钮获取中文摘要

Computer memory is structured in layers, for example (moving from inner to outer registers, "main" memory/RAM, and disk. Each is slower but larger than those within it. These layers are reflected in the design of conventional programming languages (respectively, by local variables, non-local variable and arrays, and files), and programs are designed to take best advantage of their relative speed, size, and persistency. Functional or applicative programming languages are most promising for parallel processing, but they do not yet deal with this layering of memory. Rather, present practice there is to treat all memory as RAM, structured as a "heap" for linked data structures, even though this unilevel model restricts their utility. Furthermore, although linked structures are very attractive for partitioning problems among processors, parallel heap management is an open problem. This project explores methods of reconciling the necessary layering of physical memory into the practice of purely functional programming. One goal is to demonstrate performance of reference-counting memory (RCM) hardware, which can manage a heap shared by many processors. Reckoning at the memory address--remotely from any processor--it recovers most unused memory without any processor synchronization and little additional communication. Another goal is to implement a persistent file system within a purely functional language. Persistency requires that files survive certain unpredictable failures. Therefore, the system must retain current state of the files, even though the concept of state is forbidden in functional programming.