|
|
|
| introduction | plans |
|---|
Shared memory coherence can be supported by a wide range of underlying systems, ranging from a purely software-based approach on message-passing hardware to a fully hardware-based approach on a large, cache-coherent multiprocessor. The software-based approach is inexpensive but limited in performance. The hardware-based approach has the potential to perform much better, but at significantly higher cost in development time and purchase price. The Cashmere project is predicated on the hypothesis that the best price-performance will be found, not at either of these extremes, but with an intermediate option in which hardware provides very low-latency, user-level access to the main memory of remote nodes, but does not itself maintain coherence.
The Cashmere project has developed a family of coherence protocols. All share the following characteristics:
Our early simulation-based work [KoSc96, KoSB95, KoS95a, KoS95b, KoS95c] assumed several hardware characteristics not present on the Memory Channel:
The principal challenge for our first Memory-Channel version of Cashmere was to accommodate the differences in underlying hardware model. We continued to treat each processor as if it were a separate node, ignoring intra-node hardware coherence (hence the 1L -- "one level" -- in the protocol name). We replicated all directory entries on all nodes, and arranged to broadcast all updates. Most significantly, we arranged to create a local copy of each accessed page on an initial miss. Cache fills then came from this local copy. To propagate changes to home nodes, we modified applications at the assembly-language level to double every store to shared memory, replacing the instruction with a short instruction sequence that writes to both the local copy and (via the Memory Channel) to the home node copy. Finally, to allow a node to retrieve the home node copy in response to a page fault, we implemented a fast, polling-based remote message system.
The principal question on our minds, given the scope of these changes and the relatively limited cross-sectional bandwidth of the first-generation Memory Channel, was whether the protocol would perform well enough to even approach the performance of traditional DSM protocols. To answer this question, we implemented a Memory-Channel version of TreadMarks, the best existing message-based S-DSM system. Our TreadMarks implementation relies on fast, user-level messages, but does not otherwise exploit the capabilities of the hardware. To explore the importance of bandwidth for Cashmere, we also implemented a non-doubling version of the protocol based on TreadMarks-style twins and diffs, and a protocol optimization that would eliminate protocol overhead for nominally-shared pages that were in fact used by only one processor. Performance results, reported in detail at ISCA'97 [KHSH97], indicate that diff-based version of the Cashmere-1L approaches and often exceeds the performance of TreadMarks on our cluster:
Absent any protocol or hardware changes, these results do not make a compelling case for using Cashmere instead of TreadMarks. We argued, however, that the write-doubling version of Cashmere-1L was disproportionately affected by the small first-level cache of the 21064A processor, and that even the diff-based version was handicapped by limited network bandwidth. Both of these factors are expected to improve dramatically in future generations of the hardware.
Our next major step was to build a "two-level" protocol that would take advantage of hardware coherence within nodes. In this new protocol there is a single local copy of each actively-shared page. To reduce demands for network bandwidth and cache footprint, we eliminated write-through and doubling, opting instead for TreadMarks-style diffs. At a release point, a processor in Cashmere-2L compares a modified page to a clean copy known as a twin, and applies the modifications to the master copy at the home node. At a page fault following an invalidation, a processor that needs to access a page that is already in use (by another processor) on the local node must bring in any modifications that have been made on other nodes. To avoid the need to synchronize with other local processors, we developed a novel mechanism based on reverse diffs to update all and only the modified words, in parallel with continued execution on other local processors. We also developed lock-free data structures for most of the protocol meta-data, to minimize the need for inter-node synchronization. Performance results, reported in detail at SOSP'97 [SDHH97], indicate that the two-level protocol realizes significant performance gains with respect to its one-level predecessor on many applications:
Since writing the SOSP paper, we have implemented several improvements to the Cashmere system. To eliminate restrictions on data-set size, we have moved both local and home node copies of shared data out of Memory Channel space. Memory Channel regions are now used only for synchronization objects, page directories, write notice queues, and messaging flags and buffers. As part of the move, we had to abandon the direct, word-at-a-time application of diffs to home node copies. Now a releasing processor sends a diff message to the home node, where some local processor applies the changes actively. Somewhat to our surprise, these changes had only a very minor affect on performance.
In an attempt to improve performance for certain classes of applications, we have implemented a home node migration algorithm. This addition to the protocol allows migratory data to move to the processor that is actively writing it, eliminating much of the traffic to home nodes.
A major goal of our research is to develop an integrated compile-time and run-time system for efficient shared memory parallel computing on distributed memory machines [LDCZ97, CMSD97, LCDR97, CDLZ97, ACDZ97]. The combined system presents to the user a shared memory programming model, with its well-known benefits in terms of ease of use. The run-time system (currently TreadMarks) implements a consistent shared memory abstraction using memory access detection and automatic data caching. The compiler improves the efficiency of the shared memory implementation by directing the run-time system to move large blocks of data whenever possible, thereby avoiding significant amounts of fixed, per-block overhead. To provide such directions, the compiler analyzes shared memory accesses and transforms the code to insert calls to the run-time system that provide it with the access information computed by the compiler. The run-time system is augmented with the appropriate entry points to use this information to implement bulk data transfer and to reduce the overhead of run-time consistency maintenance.
In those cases where the compiler analysis succeeds for the entire program, we have demonstrated that the combined system achieves performance comparable to that produced by compilers that directly target message passing. We have also explored the possibility of support for irregular accesses in the DSM run-time, and demonstrated the performance of the system in comparison to the current state-of-the-art for handling such accesses -- the inspector-executor approach. If the compiler analysis fails entirely, we rely on the run-time's maintenance of shared memory, and thereby avoid the complexity and the limitations of compilers that directly target message passing. The result is a single system that combines efficient support for both regular and irregular memory access patterns.
Software DSM supports irregular computation through demand fetching of data in
response to memory access faults. With the addition of a very limited form
of compiler support, namely the identification of the section of the
indirection array accessed by each processor, many of these on-demand page
fetches can be aggregated into a single message, and prefetched prior to the
access fault.
We have measured the performance of this approach for two irregular
applications, moldyn and nbf.
We find that it has similar performance to the
inspector-executor method supported by the CHAOS run-time library, while
requiring much simpler compile-time support. For moldyn,
it is up to 23%
faster than CHAOS, depending on the input problem's characteristics; for
nbf, it is no worse than 14% slower. If we include the
execution time of
the inspector, the software DSM-based approach is always faster than
CHAOS. The advantage of this
approach increases as the frequency of changes to the indirection
array increases.
The disadvantage is the potential for false sharing overhead
when the data set is small or has poor spatial locality.
We have also evaluated the use of software distributed shared memory (DSM) on a message passing machine as the target for a parallelizing compiler. We compare this approach to compiler-generated message passing, hand-coded software DSM, and hand-coded message passing. We used the APR shared-memory (SPF) compiler to generate the shared memory programs, and the APR XHPF compiler to generate the message passing programs. On the regular programs, both the compiler-generated and the hand-coded message passing outperform the shared memory versions: the compiler-generated message passing by 5.5% to 40%, and the hand-coded message passing by 7.5% to 49%. On the irregular programs, the shared memory versions outperform the compiler-generated message passing by 38% and 89%, and only slightly underperform the hand-coded message passing, differing by 4.4% and 16%. We also identified the factors that account for the performance differences, estimated their relative importance, and described methods to improve the performance.
Based on these results, we are currently developing an interface to the DSM system that can be used as the target of a parallelizing compiler. One critical issue for achieving good performance in any parallel system is load balancing, even more so in workstation environments where the machines might be shared among many users. We have preliminary results to corroborate the viability of building a system that combines compiler and run-time support to achieve load balancing dynamically on software distributed shared memory programs. We use information provided by the compiler to help the run-time system distribute the work of the parallel loops, not only according to the relative power of the processors, but also in such a way as to minimize communication and page sharing. This same (access pattern) information is also used to optimize communication whenever possible by tailoring it to the underlying system.
We are also examining issues of heterogeneity, and the run-time issues involving sharing across disparate processes [PaDw98]. We are developing a framework to support interactive client-server applications. The key to our framework is an efficient mechanism to facilitate client-controlled consistency and sharing of objects between clients and servers. Advantages are two-fold: the ability to cache relevant data on the client to better help support interactivity, and the ability to extend the computation boundary to the client to reduce the load on the server. We have preliminary results on the efficiency and usefulness of the framework when applied to the interactive data-mining domain. The interface eliminates the complexity of determining exactly what data to communicate among clients and servers, as well as when that data must be communicated. Although we have motivated our framework using the data-mining domain, we believe that its applications are more far-reaching, and will simplify and ease the development of a large number of interactive applications.
We have made significant progress in two "real world" application areas: data mining and computer vision (probabilistic search and object recognition). We designed and analyzed the performance of a parallel real-time vision-based probabilistic search algorithm used to solve the correspondence problem. This work brought out some interesting results indicating the coherence protocol needs of such applications. We also have a preliminary implementation of a parallel object recognition algorithm. The object recognition system uses a large database (several gigabytes) composed of curve features representing various objects. An input image is decomposed into its curve elements and the strongest curves are matched against curves stored in the database to generate hypotheses about object identities and poses in the input image. The matching process in the database takes a large amount of time, most of it spent reading the database. The database is initially split with approximately the same number of elements in each partition and divided up among the processes. Each process is provided the key to search for and performs the search in its partition of the database. The lists of matches found by each thread are then concatenated and used to compose the hypotheses. The parallelization follows a manager-worker model, where the work is distributed by the manager when needed. Each worker performs the search in the database, resynchronizing with the manager when done. The manager combines the generated lists and continues with the rest of the program. Efforts are currently under way to parallelize part of the hypothesis generation routines in a similar manner, and to determine the performance of the parallelization strategy.
In the data mining domain, one area we have examined is the discovery of association rules[PZLi97, ZHAg98, ZPLi97]. Association mining is the process of identifying commonly-occuring subsets in a database whose elements are sets. (For example, in a database of grocery purchases, milk and eggs might often appear together.) Our algorithms are a result of a detailed study of the available parallelism and the properties of associations. The algorithm uses a graph-theoretic (lattice) representation of common item sets, and to partition these sets among the processors. At the same time it uses a novel database layout that clusters related transactions together, and selectively replicates the database so that the portion of the database needed for the computation of associations is local to each processor. After the initial set-up phase, the algorithm eliminates the need for further communication or synchronization, and balances the computation and data across the processors. The application uses complex pointer-based data structures that typically suffer from sub-optimal locality. We found that for effective parallelization, attention needed to be paid to memory placement for improved locality and false sharing avoidance.
|
|
|
| introduction | plans |
|---|
Last Change: 11 March 1998 / scott@cs.rochester.edu