High-Performance Computation of Optimal Network Flows

最优网络流的高性能计算

• 批准号: 9306807
• 负责人: Robert Meyer
• 金额: $ 17.23万
• 依托单位: University of Wisconsin-Madison
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1993
• 资助国家: 美国
• 起止时间: 1993-08-15 至 1997-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9306807&HistoricalAwards=false
• 关键词: Performance; Computation; Optimal; Network; Flows

Historically, parallel computers have focussed on a single mode of parallelism: Multiple-Instruction Multiple-Data (MIMD) Single-Instruction, Multiple Data (SIMD). Some new computers efficiently implement both paradigms in a single integrated ``universal'' architecture capable of supporting large numbers of powerful processing nodes in a design scalable to teraflop computation. Clearly, this capability to perform well on both SIMD and MIMD computation is the basis for many future high-performance architectures. This hybrid parallelism is also ideally suited for implementing many algorithms for large-scale mathematical programming, since these methods require powerful individual processors for the solution of optimization subproblems (which may take the form of a medium-sized linear or quadratic program), efficient message passage capabilities for the transfer of subproblem solutions, and efficient synchronization and SIMD-style operations across processors. Proper algorithmic design thus allows the solution of optimization ``megaproblems'' that were intractable on preceding architectures. This project focuses on network-related optimization problems because such problems arise in a great variety of real world applications for which there are real data as well as problem generators.

从历史上看，并行计算机一直专注于 单模式并行：多指令多数据（MIMD） 单指令多数据（SIMD）。 一些新 计算机在单个集成电路中有效地实现了这两种范例 能够支持大量强大处理的“通用”架构 设计中的节点可扩展到万亿次运算。 显然，这种能力 在SIMD和MIMD计算两者上良好地执行是许多未来高性能架构的基础。 这种混合并行是 也非常适合于实现许多算法的大规模 数学规划，因为这些方法需要强大的个人处理器 对于优化子问题的解决方案（其可以采取 中等规模的线性或二次规划）、有效的消息传递能力 子问题解决方案的传输，以及有效的同步和 跨处理器的SIMD式操作。 因此，适当的算法设计允许 最优化“大问题”的解决方案， 以前的建筑。 这个项目的重点是网络相关的优化问题 因为这样的问题出现在各种各样的真实的世界应用中 其中有真实的数据以及问题生成器。