next up previous
Next: STL-user Layer Up: STXXL Design Previous: AIO Layer Implementations.

Block Management (BM) Layer

As already mentioned above, the BM layer provides an implementation of the central concept in I/O-efficient algorithms and data structures: block of elements (typed_block object). Besides, it includes a toolbox for allocating, deallocating, buffered writing, prefetching, and caching of blocks. The external memory manager (object block_manager) is responsible for allocating and deallocating external memory space on disks. The manager supports four parallel disk allocation strategies: simple striping, fully randomized, simple randomized [6], and randomized cycling [37].

The BM layer also delivers a set of helper classes that efficiently implement frequently used sequential patterns of interaction with (parallel disk) external memory. The optimal parallel disk queued writing [21] is implemented in the buffered_writer class. The class operates on blocks. buf_ostream class is build on top of buffered_writer and has a high level interface, similar to the interface of STL output iterators. Analogously, classes block_prefetcher and buf_istream contain an implementation of an optimal parallel disk prefetching algorithm [21]. The helper objects of the BM layer support overlapping between I/O and computation, which means that they are able to perform I/O in the background, when user thread is doing useful computations.

The BM layer views external memory as a set of large AIO files -- one for each disk. We will refer to these files as disks. The other approach would be to map a related subset of blocks (e.g. those belonging to the same data structure) to a separate file. This approach has some performance problems. One of them is as follows: since those (numerous) files are created dynamically, during the run of the program, the file system allocates the disk space on demand, that might in turn introduce severe uncontrolled disk space fragmentation. Therefore we have chosen the ``one-large-file-per-disk'' approach as our major scheme. However the design of our library does not forbid for data structures to store their content in separate user data files (e.g., as an option, stxxl::vector can be mapped to a user file, see Section 2.3).

The external memory manager (object block_manager) is responsible for allocating and deallocating external memory space on the disks. The block_manager reads information about available disks from the STXXL configuration file. This file contains the location of each disk file, the sizes of the disks, and file access method for each disk. When allocating a bunch of blocks, a programmer can specify how the blocks will be assigned to disks, passing an allocation strategy function object. The block_manager implements the first fit allocation heuristic. When an application requests several blocks from a disk, the manager tries to allocate the blocks contiguously. This reduces the bulk access time. On allocation requests, the block_manager returns BID objects - Block IDentifiers. An object of type BID describes the physical location of an allocated block, including the disk and offset of a region of storage on disk. One can load or store the data that resides at the given by BID location using asynchronous read and write methods of a typed_block object.

The full signature of the STXXL ``block of elements'' class is typed_block<RawSize,T,NRef,InfoType>. The template parameter RawSize defines the total size of the block in bytes. Since block size is not a fixed global constant in STXXL, a programmer can simultaneously operate with several block types having different blocks sizes. A critical requirement for many external memory data structures is that a block must be able to store links to other blocks. An STXXL block can store NRef objects of type BID. Additionally, one can equip a block with a field of type InfoType, that can hold some per-block information. Block elements of type T can be easily accessed by the array operator [] and via random access iterators.

In Listing 2 we give an example how to program block I/O using objects of the BM layer. In Line 2 we define the type of block: its size is one megabyte and the type of elements is double. The pointer to the only instance of the singleton object block_manager is obtained in Line 5. Line 6 asks the block manager to allocate 32 blocks in external memory. The new_blocks call writes the allocated BIDs to the output iterator, given by the last parameter. The std::back_inserter iterator adapter will insert the output BIDs at the end of the array bids. The manager assigns blocks to disks in a round-robin fashion as the striping() strategy suggests. Line 7 allocates 32 internal memory blocks. The internal memory allocator new_alloc<block_type> of STXXL allocates blocks on a virtual memory page boundary, which is a requirement for unbuffered file access. Along Lines 8-10 the elements of blocks are filled with some values. Then the blocks are submitted for writing (lines 11-12). As in the AIO example, I/O is overlapped with computations in function do_something(). After the completion of all write requests (Line 14) we perform some useful processing with the written data (function do_something1()). Finally we free the external memory space occupied by the 32 blocks (Line 16).

caption={Example of how to program using the BM laye...
...cks(bids.begin(), bids.end());// deallocate ext. memory (*@

next up previous
Next: STL-user Layer Up: STXXL Design Previous: AIO Layer Implementations.
Roman Dementiev 2005-08-09