Ab Initio Software Corporation

Cliff Lasser

Craig W Stanfill

Robert D Lordi

A parallel virtual file system for parallel processing systems including single-processor systems having multiple storage devices. The invention manages partitioned files as follows: (1) partitions of a partitioned file are stored in a set of isomorphic 'data trees'; (2) an additional directory tree, called the 'control tree', is used to build a model of the intended structure of the data trees; (3) the combination of a control tree and a collection of data trees is referred to as a 'multifile system', with sets of files referred to as 'multifile' and sets of directories referred to as 'multi-directories;' data elements of a multifile or multidirectory are referred to as 'data plies' and control elements of a multifile or multidirectory are referred to as 'control plies'; (4) a set of multifile subroutines is provided for accessing and modifying the multifile system in such a way so as to preserve the isomorphic data structures for the partitioned data; (5) the multifile subroutines use a distributed computing environment which provides for remote procedure calls and, in one of the embodiments of the invention, for a distributed transaction processing protocol to ensure atomicity of structural changes to the multifile system; (6) interference of concurrent file system operations is prevented by creating a 'transactional' lock for each file system.

Parallel virtual file system

Two methods for partitioning the work to be done by a computer program into smaller pieces so that checkpoints may be done more frequently. Initially, a parallel task starts with one or more input data sets having q initial partitions, divides the input data sets into p partitions by some combination of partitioning elements (i.e., partitioners/gatherers), runs an instance of a component program on each of the p partitions of the data, and produces one or more sets of output files, with each set being considered a partitioned data set. The invention is applied to such a task to create a new, 'overpartitioned' task as follows: (1) the partitioner is replaced with an 'overpartitioner' which divides its q inputs into n*p partitions, for some integer factor n; (2) the component program is run in a series of n execution phases, with p instances of the component program being run at any time. In each phase, each instance of the component program will read one overpartition of the input data and produce one partition of output data; (3) at the end of each of the n execution phases, the system is quiescent and may be checkpointed. A first embodiment explicitly overpartitions input data by using known partitioner programs, communication channels, and gatherer programs to produce overpartitioned intermediate files. The second embodiment dynamically overpartitions input data by arranging for the component programs to consecutively read contiguous subsets of the original input data.

Overpartitioning system and method for increasing checkpoints in

Methods and systems for running and checkpointing parallel and distributed applications which does not require modification to the programs used in the system nor changes to the underlying operating system. One embodiment of the invention includes the following general steps: (1) starting an application on a parallel processing system; (2) controlling processes for the application, including recording of commands and responses; (3) controlling a commit protocol; (4) detecting failures of the application; (5) continuing execution of the application from the most recently committed transaction after 'replaying' the recorded commands and responses. A second embodiment comprises the following general steps: (1) starting an application on a parallel processing system; (2) controlling processes for the application, including recurrent recording of the memory image of a driver program that controls the application; (3) controlling a commit protocol; (4) detecting failures of the application; (5) continuing execution of the application from the most recently committed transaction after 'restoring' the recorded memory image of the driver program.

Growing community of inventors

Cambridge, MA, United States of America

Cliff Lasser