Ring optimization for data sieving writes

In one embodiment, a method and apparatus for ring optimization for data sieving writes is disclosed. The method includes dividing a file range to be written to via a data sieving write operation into N groups, where N is greater than or equal to a number of processes writing to the memory, determining an offset assigned to each process, the offset being a distance from a beginning of the file range at which each process starts its writing, simultaneously writing by each process to the group of the file range determined by the associated offset of each process, and moving, by each process, to the next available subsequent group when a process completes the writing. Other embodiments are also disclosed.

FIELD OF INVENTION

An embodiment of the invention relates to parallel input/output performed by computer applications, and more specifically, to a ring optimization for data sieving writes.

BACKGROUND OF INVENTION

A parallel application that includes several processes may perform input/output (I/O) collectively and in parallel. Frequently, the collective I/O may read or write an entire file, although each process accesses only a subset of the file contents. In some cases, the subset of the file accessed by one process may be interleaved with the subsets accessed by other processes. Further, the data may be arranged in memory for processing differently than in the file. Because of the potential complexity of data rearrangement and the need to synchronize the operation of multiple processes, it can be difficult to complete a collective I/O operation quickly.

One solution to this problem is data sieving. Data sieving is a way of combining multiple I/O requests into one request so as to reduce the effect of high I/O latency time. Data sieving for reads involves each process independently reading large blocks from a file and extracting its own relevant data. For writes, each process participating in the data sieving must lock a range of the file (gaining exclusive access), read the previous file contents in that range, insert its own data, write the updated data to the file, and release the lock. These steps are repeated by each process until the entire file range being collectively written has been updated. The locking required limits parallelism, and hence the speed at which the file can be written, because other processes will not be able to access that portion of the file until the lock is released.

A mechanism to reduce lock contention and improve the speed of parallel writes to a file by reducing the amount of time that multiple processes utilizing a data sieving algorithm are trying to update the same range within a file would be beneficial.

SUMMARY OF INVENTION

The present invention includes novel methods and apparatus for ring optimization for data sieving writes.

According to one embodiment of the invention, a method is disclosed. The method includes dividing a file range to be written to via a data sieving write operation into N groups, where N is greater than or equal to a number of processes writing to the memory, determining an offset assigned to each process, the offset being a distance from a beginning of the file range at which each process starts its writing, simultaneously writing by each process to the group of the file range determined by the associated offset of each process, and moving, by each process, to the next available subsequent group when a process completes the writing.

According to another embodiment of the invention, an apparatus is disclosed. The apparatus includes one or more processes accessing a file range via a collective input/output (I/O) data sieving algorithm and an interface to a file. The interface to the file is further to: divide the file into N groups, where N is greater than or equal to a number of the one or more processes writing to the file; determine an offset assigned to each process, the offset being a distance from a beginning of the file at which each process starts its writing; simultaneously write by each process to the group of the file determined by the associated offset of each process; and move, by a process, to the next available subsequent group when the process completes its writing.

DETAILED DESCRIPTION

A method and apparatus are described for ring optimization for data sieving writes. According to one embodiment, the method includes dividing a file range to be written to via a data sieving write operation into N groups, where N is greater than or equal to a number of processes writing to the memory, determining an offset assigned to each process, the offset being a distance from a beginning of the file range at which each process starts its writing, simultaneously writing by each process to the group of the file range determined by the associated offset of each process, and moving, by each process, to the next available subsequent group when a process completes the writing.

In the following description, numerous details are set forth. It will be apparent, however, to one skilled in the art that embodiments of the present invention may be practiced without these specific details. In other instances, well-known structures, devices, and techniques have not been shown in detail, in order to avoid obscuring the understanding of the description. The description is thus to be regarded as illustrative instead of limiting.

Reference in the specification to “one embodiment” or “an embodiment” means that a particular feature, structure, or characteristic described in connection with the embodiment is included in at least an embodiment of the invention. The appearances of the phrase “in one embodiment” in various places in the specification are not necessarily all referring to the same embodiment.

Also, select embodiments of the present invention include various operations, which are described herein. The operations of the embodiments of the present invention may be performed by hardware components or may be embodied in machine-executable instructions, which may be in turn utilized to cause a general-purpose or special-purpose processor, or logic circuits programmed with the instructions, to perform the operations. Alternatively, the operations may be performed by a combination of hardware and software.

Moreover, embodiments of the present invention may be provided as computer program products, which may include machine-readable medium having stored thereon instructions used to program a computer (or other electronic devices) to perform a process according to embodiments of the present invention. The machine-readable medium may include, but is not limited to, floppy diskettes, hard disk, optical disks, CD-ROMs, and magneto-optical disks, read-only memories (ROMs), random-access memories (RAMs), erasable programmable ROMs (EPROMs), electrically EPROMs (EEPROMs), magnetic or optical cards, flash memory, or other types of media or machine-readable medium suitable for storing electronic instructions and/or data. Moreover, data discussed herein may be stored in a single database, multiple databases, or otherwise in select forms (such as in a table).

Embodiments of the invention introduce a novel method for ring optimization for data sieving writes. The ring optimization presented in embodiments of the invention reduces lock contention, and hence improves the speed of parallel writes to a file, by reducing the amount of time that multiple processes are trying to update the same range within a file. This allows for more parallelism and faster writes to a file when a data sieving algorithm is used.

FIG. 1is a block diagram illustrating one embodiment of data sieving and collective I/O in parallel computing applications. In some embodiments, the parallel computing applications utilize the Message Passing Interface (MPI) programming interface, and more specifically utilize the MPI-IO programming interface. Parallel computing applications typically access a large number of small, non-contiguous pieces of data from a file. For good I/O performance, the size of an I/O request should be large. Otherwise, the I/O performance suffers considerably if applications access data by making many small I/O requests to access only a single contiguous chunk of data at a time.

To reduce the effect of high I/O latency, it is important to make as few requests to the file system as possible. A data sieving algorithm may be utilized to accomplish this purpose. With reference toFIG. 1, assume that an application has made a single write request to update five non-contiguous pieces of data represented by line110. The five non-contiguous pieces of data are represented by110athrough110e.

Instead of writing each piece110a-110eseparately, a data sieving algorithm reads a single contiguous chunk of data120starting from the first requested byte up to the last requested byte into a temporary buffer in memory. Then, it replaces the requested portions130a-130ein the temporary buffer from the applications' buffer130. If the application contains multiple processes, the portion of the file being accessed must also be locked during this read-modify-write operation to prevent concurrent updates by other processes.

In the case of a collective I/O operation, many parallel applications may need to access several non-contiguous portions of a file. In such a situation, the requests of different processes are often interleaved110a-110eand may together span the large contiguous portion of the file120. A collective I/O operation can improve I/O performance by merging the requests of different processes and servicing the merged request via the data sieving algorithm.

For instance,110a,110cand110emight be written by a first process;110band110dmight be written by a second process. Each of these processes would read the single contiguous chunk of data120into their temporary buffer, update it from their application buffer130, and write the data120back to the file. To ensure that the updates are made correctly, each process would lock the range120before the read, unlocking it only after the write. This limits the range120to being updated by a single process at a time.

Typically, the amount of data being written exceeds the maximum size of the temporary buffer. In this case, the range being updated will be divided into ranges according to the temporary buffer size (with their offset and size typically rounded to match I/O alignment requirements). For instance, the portion of the file from110athrough the end of110cmight be contained in one range, while the portion of the file from the end of110cthrough the end of110emight be contained in another range. Each process then updates each of the ranges, performing the lock, read, update, write, and unlock sequence on each range in turn.

However, the above collective I/O data sieving algorithm may lead to lock contention when writing because each process writes its data into the file in the order that the data appears in the file. Thus, at the beginning of the data sieving process, all processes may try to access the first range of the file. However, only one process may lock this range at a time, so all other processes are blocked until the first process proceeds.

One approach taken to reduce this lock contention is to use smaller buffers (and hence more ranges), so that there are fewer processes competing to update each range in the file. But, this reduces overall I/O performance and is not effective when data from all processes is interleaved at fine granularity within the file.

Embodiments of the invention utilize a ring optimization for data sieving writes to avoid the above-mentioned problems.FIG. 2is a flow diagram depicting a method of ring optimization for data sieving writes according to embodiments of the invention. The ring optimization process200begins at processing block210, where multiple processes of an application prepare to write to a file range by invoking a collective I/O data sieving algorithm. The collective I/O data sieving algorithm may be the same as discussed above with respect toFIG. 1.

At processing block220, the file range being written is divided into N groups, where N is greater than or equal to the number of processes updating the file. In some embodiments, the ranges may be of variable size or alignment. For instance, they may be of a size to round the necessary buffer size to a value that is optimum for disk access. In one embodiment, the ranges do not overlap.

At processing block230, an offset is determined for each process trying to update the file range. The offset defines a distance from the beginning of the file range at which each process may start its update. To avoid contention, the offset should be unique to each process. In some embodiments, the offset may be determined by a rank assigned to the particular process. For instance, a process may be assigned a rank when it is initialized as part of the parallel application.

At processing block240, each process locks, reads if necessary, and begins updating the particular group of the file range associated with the offset assigned to each process. When a process completes its writing and releases its lock, it moves to the next subsequent available group at processing block250. In some embodiments, a process may skip a group of the file range that is locked and return to that group at a later time.

Finally, at processing block260, the update to the file continues by each process moving forward through the file in a circular fashion. For instance, when the end of the range is reached, a process may move to the start of the range and continues to write its updates into the file until it has updated all necessary groups. In some embodiments, a backward-stepping direction may be utilized. One skilled in the art will appreciate that any ordering direction that visits each group exactly once will also provide the benefits of the ring optimization of embodiments of the invention.

FIGS. 3A through 3Eare block diagrams illustrating one embodiment of a step-by-step application of ring optimization for data sieving writes to memory. In one embodiment,FIGS. 3A through 3Eillustrate the application of process200described with respect toFIG. 2to a file.FIG. 3Adepicts a file write operation for multiple processes under a traditional data sieving approach, such as the one described with respect toFIG. 1. In this case, all four processes,302,304,306,308, would first try to write their data to range1310, followed by writes to range2320, range3330, and range4340in sequential order, with each process attempting to update each range at the same time. This would lead to the above described lock contention problem.

Under the ring optimization approach of embodiments of the invention, such as process200described with respect toFIG. 2, this lock contention problem is avoided.FIG. 3Bdepicts the initial starting point for the data sieving algorithm under a ring optimization approach. Process1302would first write its data to range1310, while process2304simultaneously writes to range2320, process3306to range3330, and process4308to range4340.

FIGS. 3C through 3Edepict the remaining process for the ring optimization.FIGS. 3C,3D, and3E show how each process302-308continues on to the next available subsequent range310-340after they complete their previous write to a range, and then lock and begin writing the next range. As there is no requirement for the processes to start at a particular point in the data range or write in a particular order, this optimization allows lock contention to be avoided and write efficiency improved.

One skilled in the art will appreciate that the synchronization of writes in the ring optimization need not be in lock-step if multiple buffers are used within each range. In fact, explicit synchronization is not required between the processes at all. Logically, implicit synchronization results through the file range locks and the circular forward stepping of the processes through the ranges.

FIG. 4illustrates an exemplary computer system400in which certain embodiments of the present invention may be implemented. In one embodiment, the process ofFIG. 2may be implemented by system400or by components of system400.

System400comprises a central processor402, a main memory404, an input/output (I/O) controller406, a keyboard408, a pointing device410(e.g., mouse, track ball, pen device, or the like), a display device412, a mass storage414(e.g., a nonvolatile storage such as a hard disk, an optical drive, and the like), and a network interface418. Additional input/output devices, such as a printing device416, may be included in the system400as desired. As illustrated, the various components of the system400communicate through a system bus420or similar architecture.

In a further embodiment, system400may be a distributed computing system. In other words, one or more of the various components of the system400may be located in a physically separate location than the other components of the system400. Such components may be accessed and connected via a network to the other components.

In accordance with an embodiment of the present invention, the computer system400includes a Sun Microsystems computer utilizing a SPARC microprocessor available from several vendors (including Sun Microsystems, Inc., of Santa Clara, Calif.). Those with ordinary skill in the art understand, however, that any type of computer system may be utilized to embody the present invention, including those made by Hewlett Packard of Palo Alto, Calif., and IBM-compatible personal computers utilizing Intel microprocessor, which are available from several vendors.

Also, instead of a single processor, two or more processors (whether on a single chip or on separate chips) can be utilized to provide speedup in operations. It is further envisioned that the processor402may be a complex instruction set computer (CISC) microprocessor, a reduced instruction set computing (RISC) microprocessor, a very long instruction word (VLIW) microprocessor, a processor implementing a combination of instruction sets, and the like.

The network interface418provides communication capability with other computer systems on a same local network, on a different network connected via modems and the like to the present network, or to other computers across the Internet. In various embodiments of the present invention, the network interface418can be implemented utilizing technologies including, but not limited to, Ethernet, Fast Ethernet, Gigabit Ethernet (such as that covered by the Institute of Electrical and Electronics Engineers (IEEE) 801.1 standard), Infiniband, Myrinet, scalable coherent interconnect (SCI), wide-area network (WAN), leased line (such as T1, T3, optical carrier 3 (OC3), and the like), analog modem, digital subscriber line (DSL and its varieties such as high bit-rate DSL (HDSL), integrated services digital network DSL (IDSL), and the like), cellular, wireless networks (such as those implemented by utilizing the wireless application protocol (WAP)), time division multiplexing (TDM), universal serial bus (USB and its varieties such as USB 2), asynchronous transfer mode (ATM), satellite, cable modem, and/or FireWire.

Moreover, the computer system400may utilize operating systems such as Solaris, Windows (and its varieties such as CE, NT, 2000, XP, ME, and the like), HP-UX, IBM-AIX, PALM, UNIX, Berkeley software distribution (BSD) UNIX, Linux, Apple UNIX (AUX), Macintosh operating system (Mac OS) (including Mac OS X), and the like. Also, it is envisioned that in certain embodiments of the present invention, the computer system400is a general purpose computer capable of running any number of applications such as those available from companies including Oracle, Siebel, Unisys, Microsoft, and the like.

The foregoing description has been directed to specific embodiments. It will be apparent to those with ordinary skill in the art that modifications may be made to the described embodiments, with the attainment of all or some of the advantages. Therefore, it is the object of the appended claims to cover all such variations and modifications as come within the spirit and scope of the invention.