The proceedings contain 40 papers. The topics discussed include: time vs. space trade-offs for rendezvous in trees;allowing each node to communicate only once in a distributed system: shared whiteboard models;optimal ...
ISBN:
(纸本)9781450312134
The proceedings contain 40 papers. The topics discussed include: time vs. space trade-offs for rendezvous in trees;allowing each node to communicate only once in a distributed system: shared whiteboard models;optimal and competitive runtime bounds for continuous, local gathering of mobile robots;online multi-robot exploration of grid graphs with rectangular obstacles;in search of parallel dimensions;delegation and nesting in best-effort hardware transactional memory;design, verification and applications of a new read-write lock algorithm;a lock-free B+tree;brief announcement: the problem based benchmark suite;brief announcement: subgraph isomorphism on a multithreaded shared memory architecture;efficient cache oblivious algorithms for randomized divide-and-conquer on the multicore model;a scalable framework for heterogeneous GPU-based clusters;and faster and simpler width-independent parallelalgorithms for positive semidefinite programming.
Programs written for an architecture with n processors require a re-write when migrated to an m processor architecture {(m > n)} to benefit from additional resources. Compiler based solutions do not match manual op...
详细信息
Performance matters. But how we improve it is changing. Historically, transparent hardware improvements would mean software just ran faster. That may not necessarily be true in the future. To continue the pace of inno...
详细信息
ISBN:
(纸本)9781450312134
Performance matters. But how we improve it is changing. Historically, transparent hardware improvements would mean software just ran faster. That may not necessarily be true in the future. To continue the pace of innovation, the future will need to be increasingly parallel- involving parallelism across data, threads, cores, and nodes. This talk will explore some of the dimensions of parallelism, and the opportunities and challenges they pose.
Creating components based on concurrent and parallelalgorithms and data structures often requires more attention to "engineering" issues not seen with most other libraries. Components created in the "o...
详细信息
ISBN:
(纸本)9781450312134
Creating components based on concurrent and parallelalgorithms and data structures often requires more attention to "engineering" issues not seen with most other libraries. Components created in the "obvious" way sometimes turn out to be wrong, to perform poorly, or are unusable in most applications, because the abstractions in which they are expressed are leaky, imprecise, or incorrectly specified. While many of these issues are encountered in other aspects of concurrent programming, the impact is accentuated when they continue to leak through to APIs provided by library components. This presentation surveys some examples and lessons learned from the design, implementation, and applications of the *** library, including those surrounding memory models, resource management and garbage collection, thread management, optimization, and code generation.
We present a parallel solution to the Maximum-Flow (Max-Flow) problem, suitable for a modern many-core architecture. We show that by starting from a PRAM algorithm, following an established "programmer's work...
详细信息
ISBN:
(纸本)9781450307437
We present a parallel solution to the Maximum-Flow (Max-Flow) problem, suitable for a modern many-core architecture. We show that by starting from a PRAM algorithm, following an established "programmer's workflow" and targeting XMT, a PRAM-inspired many-core architecture, we achieve significantly higher speed-ups than previous approaches. Comparison with the fastest known serial max-flow implementation on a modern CPU demonstrates for the first time potential for orders-of-magnitude performance improvement for Max-Flow. Using XMT, the PRAM Max-Flow algorithm is also much easier to program than for other parallel platforms, contributing a powerful example toward dual validation of both PRAM algorithmics and XMT.
As the gap between the cost of communication (i.e., data movement) and computation continues to grow, the importance of pursuing algorithms which minimize communication also increases. Toward this end, we seek asympto...
详细信息
ISBN:
(纸本)9781450307437
As the gap between the cost of communication (i.e., data movement) and computation continues to grow, the importance of pursuing algorithms which minimize communication also increases. Toward this end, we seek asymptotic communication lower bounds for general memory models and classes of algorithms. Recent work [2] has established lower bounds for a wide set of linear algebra algorithms on a sequential machine and on a parallel machine with identical processors. This work extends these previous bounds to a heterogeneous model in which processors access data and perform floating point operations at differing speeds. We also present an algorithm for dense matrix multiplication which attains the lower bound.
We present parallel greedy approximation algorithms for set cover and related problems. These algorithms build on an algorithm for solving a graph problem we formulate and study called Maximal Nearly Independent Set (...
详细信息
ISBN:
(纸本)9781450307437
We present parallel greedy approximation algorithms for set cover and related problems. These algorithms build on an algorithm for solving a graph problem we formulate and study called Maximal Nearly Independent Set (MANIS)-a graph abstraction of a key component in existing work on parallel set cover. We derive a randomized algorithm for MANIS that has O(m) work and O(log(2)m) depth on input with m edges. Using MANIS, we obtain RNC algorithms that yield a (1 + epsilon)H-n-approximation for set cover, a (1 - 1/e - epsilon)-approximation for max cover and a (4 + epsilon)-approximation for min-sum set cover all in linear work;and an O(log*n)-approximation for asymmetric k-center for k <= log(O(1)) n and a (1.861 + epsilon)-approximation for metric facility location both in essentially the same work bounds as their sequential counterparts.
暂无评论