EXTERNAL MEMORY IN BULK-SYNCHRONOUS PARALLEL ML

Abstra t. A fun tional data-parallel language alled BSML was designed for programming Bulk-Syn hronous Parallel algo-rithms, a model of omputing whi h allows parallel programs to be ported to a wide range of ar hite tures. BSML is based on an extension of the ML language with parallel operations on a parallel data stru ture alled parallel ve tor. The exe ution time an be estimated. Dead-lo ks and indeterminism are avoided. For large s ale appli ations where parallel pro essing is helpful and where the total amount of data often ex eeds the total main memory available, parallel disk I/O be omes a ne essity. In this paper, we present a library of I/O features for BSML and its formal semanti s. A ost model is also given and some preliminary performan e results are shown for a ommodity luster. Key words. Parallel Fun tional Programming, Parallel I/O, Semanti s, BSP. 1. Introdu tion. Some problems require performan e that an only be provided by massively parallel omputers. Programming these kind of omputers is still di ult. Many important omputational appli ations involve solving problems with very large data sets [44℄. Su h appli ations are also referred as out-of- ore appli ations. For example astronomi al simulation [47℄, rash test simulation [10℄, geographi information systems [32℄, weather predi tion [52℄, omputational biology [17℄, graphs [40 ℄ or omputational geometry [11℄ and many other s ienti problems an involve data sets that are too large to t in the main memory and therefore fall into this ategory. For another example, the Large Hadron Collider of the CERN laborator