Parallel Computing for Large-Scale Optimization

大规模优化问题出现在各种重要的科学、工程和经济应用中，并且表现出允许通过具有高度并行性的算法来求解的结构。将继续研究开发适合分布式解决这类问题的分解算法，并在各种并行结构上执行和测试这些方法，包括计算机科学部现有的多计算机和多处理器，以及通过ARPANET在其他地方提供的多计算机和多处理器。这种算法具有非常适合并行体系结构的大粒度和低数据传输特性。将特别强调网络优化问题，因为数学规划在现实世界中最困难的应用中有很大一部分属于这一类，而且这类问题也涵盖了广泛的数学类别(从线性到非线性，从凸到非凸，从确定性到随机)。这些问题的并行算法的开发还需要开发调度和负载平衡技术，这些技术将在研究其他大规模科学计算领域的分布式技术时有用。如果要有效地使用这些新的体系结构，那么在多个并行处理器上同时运行的问题的分解是必不可少的。

Large-scale optimization problems arise in a great variety of important scientific, engineering, and economic applications, and exhibit structures that allow solution via algorithms that possess a high degree of parallelism. Research will be continued in the development of decomposition algorithms appropriate for the distributed solution of such problems and in the implementation and testing of these methods on a variety of parallel architectures including the multicomputers and multiprocessors available at the Computer Sciences Department and those available elsewhere via ARPANET. Such algorithms have the large granularity and low data transfer properties that are ideally suited to parallel architectures. Particular emphasis will be given to network optimization problems, since a large proportion of the most difficult real-world applications of mathematical programming fall into this category, and since such problems also cover a broad spectrum of mathematical classes (from linear to nonlinear, from convex to nonconvex, from deterministic to stochatic). The development of parallel algorithms for these problems will also require the development of scheduling and load-balancing techniques that will be useful in the study of distributed techniques for other areas of large- scale scientific computation. The decomposition of problems to run simultaneously on multiple parallel processors is essential if these new architectures are to be effectively used.