Average-Case Parallel Algorithms, and Aspects of Architectures

平均情况并行算法和架构方面

• 批准号: 9004727
• 负责人: Quentin Stout
• 金额: $ 22.6万
• 依托单位: Regents of the University of Michigan - Ann Arbor
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1990
• 资助国家: 美国
• 起止时间: 1990-08-01 至 1994-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9004727&HistoricalAwards=false
• 关键词: Average; Case; Parallel; Algorithms; Aspects

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.

这项研究的目的是： 1.设计和分析具有快速平均案例时间的算法， 同时获得速度，更简单的算法，并开发 一个算法的分析，它匹配的做法比 通常强调最坏情况的时间。 两个细粒度的共享 内存和中等粒度的分布式内存，机器将 考虑了 这包括建模和实现 具有一系列局部/全局权衡的算法，因此， 算法可以移植到各种机器上， 优化每一个。 2.确定并发的各种抽象模型之间的关系 写，强调模型与潜在的光学实现。 3.开发问题间的约简，并开发并行算法 在一些标准问题方面，为了简化 建筑 4.开发一个与性能相匹配的分布式内存机器 在各种几何问题上的共享内存机器。