多核平台上非规则应用的并行算法和并行编程模型研究的中期报告.docx

多核平台上非规则应用的并行算法和并行编程模型研究的中期报告
摘要：
随着多核平台的普及，如何充分利用多核处理器的性能成为非常重要且紧迫的问题。非规则应用是一类常见的复杂应用，它们通常没有规则的访问模式或者控制流程，因此对并行算法和并行编程模型提出了挑战。本文介绍了基于图的并行算法和Hybrid-forth语言的并行编程模型，分析了它们在多核平台上的性能和可扩展性。实验结果表明，在多核平台上，这些方法可以显著提高非规则应用的性能，并且对于多核处理器数量的增加，它们也表现出很好的可扩展性。
关键词：多核平台；非规则应用；并行算法；并行编程模型
引言：
随着多核处理器的普及，如何充分利用多核处理器的性能成为非常重要且紧迫的问题。然而，非规则应用的并行化一直是一个具有挑战性的问题。非规则应用是一类复杂应用，它们通常没有规则的访问模式或者控制流程，因此对于并行算法和并行编程模型提出了挑战。
本文介绍了基于图的并行算法和Hybrid-forth语言的并行编程模型，并分析了它们在多核平台上的性能和可扩展性。实验结果表明，在多核平台上，这些方法可以显著提高非规则应用的性能，并且对于多核处理器数量的增加，它们也表现出很好的可扩展性。
基于图的并行算法：
基于图的并行算法是一种常用的并行化非规则应用的方法。该方法将问题抽象成一个图，每个节点表示一个计算单元，每个边表示两个计算单元之间的依赖关系。通常，基于图的并行算法采用top-down或者bottom-up的方式进行计算，从而利用多核处理器的并行能力。
在本文中，我们采用基于图的并行算法来并行化两个非规则应用：PageRank和BFS。对于PageRank算法，我们通过将网页抽象成一个图，每个网页表示一个节点，每个链接表示两个节点之间的边，从而利用多核处理器的并行能力。对于BFS算法，我们采用bottom-up的方式进行计算，从而避免了计算过程中的数据竞争。
实验结果表明，基于图的并行算法可以显著提高PageRank算法和BFS算法的性能，并且对于多核处理器数量的增加，它们也表现出很好的可扩展性。
Hybrid-forth语言的并行编程模型：
Hybrid-forth语言是一种基于Forth语言的扩展，它将Forth语言的栈操作扩展到多核处理器上，从而利用多核处理器的并行能力。
在本文中，我们采用Hybrid-forth语言来并行化一个非规则应用：Delaunay三角化算法。Delaunay三角化算法是一种常用的非规则计算，它可以将一个点集转换成一个三角形网格，从而用于科学计算和工程领域。我们采用Hybrid-forth语言实现了Delaunay三角化算法，并针对多核处理器进行了优化。
实验结果表明，Hybrid-forth语言可以显著提高Delaunay三角化算法的性能，并且对于多核处理器数量的增加，它也表现出很好的可扩展性。
结论：
本文介绍了基于图的并行算法和Hybrid-forth语言的并行编程模型，并分析了它们在多核平台上的性能和可扩展性。实验结果表明，在多核平台上，这些方法可以显著提高非规则应用的性能，并且对于多核处理器数量的增加，它们也表现出很好的可扩展性。未来我们将继续研究并优化这些方法，以进一步提高它们在多核平台上的性能和可扩展性。