High-Performance Computation of 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.