并行算法设计：分而治之与优化策略

并行算法的一般设计过程:组合-并行算法设计是由曹振南提出的，主要探讨了如何在现代计算机系统中有效地设计和实施并行算法。文章首先强调了并行计算并不是新概念，而是古老的思维在计算机科学中的扩展应用，指出并行编程可能需要时间发展和完善，类似于串行编程技术的长期积累。 文章内容涵盖了并行算法设计的多个方面，包括基础知识、并行计算的性能评测、并行算法设计的基本方法和技术。设计过程一般分为几个步骤： 1. **基本知识及现状**：介绍并行计算的历史背景和现代计算机的并行特性，如Intel和Purdue University的研究机构提供了理论和实践支持。 2. **性能评测**：评估并行计算的效能，包括降低单个问题解决时间、扩大问题规模和提升吞吐率，这些都是并行计算的主要目标。 3. **并行算法设计方法**：强调通过“分而治之”的策略，即将大任务分解成小任务，以便在多个处理器上同时执行，这有助于减少任务数量和通信量，提高效率。 4. **设计过程**：重点在于如何通过组合小任务（表面-容积效应，通信量与子域表面积成比例，计算与容积成比例），以及利用重复计算（冗余计算）来优化通信与计算的平衡。此外，保持算法的灵活性和降低软件开发成本也是设计考量的因素。 5. **硬件现状**：区分了共享内存SMP（Symmetric Multi-Processor）架构，如SGI Power Challenge和SUN E10000，这些系统通过共享内存连接处理器，适合相对较小的处理器数量。另一种是分布内存MPP（Massively Parallel Processors）计算机，由大量独立内存节点通过高速网络连接，能够支持大规模并行处理，如IBM Blue Gene等。 6. **并行编程技术**：讨论了针对这两种硬件架构的并行编程手段，如OpenMP、消息传递（MPI）、以及高性能并行功能（HPF）。 通过学习并理解并行算法的设计过程，开发者可以更好地利用现代计算机的并行能力，优化应用性能，应对日益增长的性能需求。随着硬件的进步和编程工具的发展，未来的并行计算将继续成为信息技术领域的重要研究方向。