CAREER: High-Performance Algorithms for Scientific Applications

长期以来，并行计算一直承诺提供高性能，但它只在一个狭窄的应用范围内交付。在大型分布式内存系统级别上利用并行性受到消息传递成本的阻碍，而共享内存系统大多仍然是小规模的。然而，随着对称多处理器（smp）的出现，中等规模的共享内存正在成为一种可用的商品。高性能千兆网络允许可扩展的应用程序在大型smp集群上运行。在接下来的五到十年里，smp集群很可能成为可扩展高性能计算的主要架构；然而，迄今为止，支持这些SMP集群上有效并行计算的工作还很少。我们进行的初步工作表明，有可能改进当前SMP集群的编程方法。在这个职业奖项中，目标是为不规则（例如，基于字符串、树和基于图的）计算的SMP集群开发、实现、评估和细化算法，这些算法将在SMP集群的典型配置上提供显着的加速，并随着处理器数量的增加而优雅地扩展。该研究将研究新的算法和基本例程库，以支持不规则计算，主要是基于树和图，以及如何利用PRAM算法的理论研究的新见解。基因组学、生物信息学和计算生态学中的科学驱动问题将为本研究提供重点。该项目的教育部分包括指导高中生和少数民族学生，通过演讲和论文传播研究成果，并在重要会议和研讨会上发表教程。之前的指导已经培养了几个在地方和全国比赛中获得第一名的个人和团体团队，指导将继续与少数群体开展活动，如全国黑人工程师协会和美国印第安人普韦布洛学生团体。

Parallel computing has long offered the promise of very high performance, but it has deliveredonly in a narrow range of applications. Exploiting parallelism at the level of large distributed-memorysystems is hampered by the cost of message-passing, while shared-memory systems remain mostlysmall-scale. With the advent of symmetric multiprocessors (SMPs), however, shared-memory on amodest scale is becoming an available commodity. High-performance gigabit networks allow scalable applications to run on large clusters of SMPs. Over the next five to ten years, clusters of SMPs will likely be the predominant architecture for scalable high-performance computing; however, little work has been done to date to support effective parallel computing on these SMP clusters.Preliminary work we have conducted indicates that it is possible to improve upon current programmingmethods for SMP clusters. In this career award the goal is to develop, implement, assess, andrefine algorithms for SMP clusters for irregular (e.g., string-, tree-, and graph-based) computations thatwill deliver significant speedups on typical configurations of SMP clusters and scale gracefully withthe number of processors. The research will investigate new algorithms and a library of basic routines tosupport irregular computations, mostly tree- and graph- based, along with new insights on how to leveragethe theoretical research in PRAM algorithms. Science-driven problems in genomics,bioinformatics, and computational ecology will provide the focus for this research.The education component of this project includes mentoring high school and minority students, diseminating research results through talks and papers, and presenting tutorials at key conferences andworkshops. Prior mentoring has produced several individual and group teams that have won first place in both local and national competitions and mentoring will continue activities with minority groups, such as the National Society of Black Engineers and Native American Pueblo student groups.