Average-Case Parallel Algorithms, and Aspects of Architectures

点击翻译按钮获取中文摘要

The objectives of this research are to: 1. Design and analyze algorithms with fast average-case time, simultaneously obtaining speed, simpler algorithms, and developing an analysis of algorithms which matches practice better than the usual emphasis on worst-case time. Both fine-grained shared memory, and medium-grained distributed memory, machines will be considered. This includes work on modeling and implementing algorithms with a range of local/global tradeoffs, so that such algorithms can be ported to a variety of machines and be easily optimized on each. 2. Determine relationships among various abstract models of concurrent writes, emphasizing models with potential optical implementations. 3. Develop reductions among problems, and develop parallel algorithms in terms of a few standard problems, to simplify portability among architectures. 4. Develop a distributed-memory machine which matches the performance of shared-memory machines on a variety of geometrical problems.