Scheduling Collaborative Computations on Heterogeneous Clusters

在过去的十年中，我们看到了用于各种计算的计算平台的范式转变。技术的进步和经济的考虑使得工作站集群或pc成为高性能“协作”计算（其中许多计算机合作解决单个计算问题）的可行媒介。在早期的计算环境中确保高效“协作”计算的许多算法设备不再保证此类集群中的效率，特别是当集群是异构的时候，因为它们的工作站可能在计算能力上有所不同。本文提出的研究方案致力于在异构集群中实现可证明的高效计算，通过高效的算法进行大规模的重要计算。“可证明的高效计算”目标的第一个组成部分将是使用分析和实验方法相结合的方法来开发设计调度算法所需的见解，这些算法的性能可以通过严格的数学和/或统计分析来预测。目标的第二个组成部分将是验证用于制定和分析算法的抽象模型。算法在实际集群上的实现，以及将测量的性能与抽象算法模型的预测进行比较，将用于验证或在必要时修改模型。在此过程中产生的调度算法和适当的实现将是研究的主要成果。拟议中的研究将集中在“特设”集群上，即由“现成的”工作站或个人电脑组装而成，通过局域网相互连接。这里的主要调度挑战在于工作站间通信的大量成本和集群（可能）的异构性，即其组成工作站的计算能力的差异。最初的研究已经为拟议的研究提供了一个数学框架。技术的影响。提出的工作将为在异构集群上有效地调度各种重要的计算问题提供严格验证的指导方针。研究成果将在主要会议和期刊上发表，并将纳入课程和研讨会。通过对学生的培训，以及与美国和国外同事的合作和技术互动，这项工作将导致进一步的技术进步。（目前正在与澳大利亚、法国和意大利的同事合作。）更广泛的影响。美国国家科学基金会之前的支持已经导致将尖端技术材料纳入独立研究，课程和研究研讨会，这已经成为马萨诸塞大学阿默斯特分校几个部门几代学生培训的一部分。除了一名博士生外，PI的所有博士生都在美国的学院或大学追求（成功的）学术生涯。最近有两位女博士生：一位出生在中国，另一位出生在东欧；两人都成功地在美国教育机构寻求职业发展。拟议研究的结果将以与先前结果相同的方式纳入教育计划。

Rosenberg, AronldUniversity of Massachusetts AmherstCCF-0342417The past decade has seen a paradigm shift in the computing platforms used for a wide variety of computations. Advances in technology and economic considerations have made clusters of workstations or pc's a viable medium for high-performance "collaborative'' computing (wherein many computers cooperate to solve a single computational problem). Many of the algorithmic devices that ensured efficient "collaborative'' computing in earlier computing environments no longer guarantee efficiency within such clusters, especially when the clusters are heterogeneous, in the sense that their workstations may differ in computational power. The program of research proposed herein is dedicated to achieving provably efficient computation in heterogeneous clusters, via efficient algorithms for large classes of important computations. The first component of the goal of "provably efficient computation'' will be the use of a combination of analytical and experimental methods to develop the insights needed to craft scheduling algorithms whose performance is predictable via rigorous mathematical and/or statistical analyses. The second component of the goal will be to validate the abstract models used to formulate and analyze algorithms. Implementations of algorithms on actual clusters, and comparison of measured performance against the predictions of the abstract algorithmic models, will be used to validate or, where necessary, to modify the models. The scheduling algorithms and, when appropriate, implementations thereof that result from this process will be the main product of the research.The proposed research will focus on "ad hoc'' clusters, which are assembled from "off the shelf'' workstations or pc's, interconnected via local-area networks. The major scheduling challenges here reside in the substantial cost of interworkstation communication and in the cluster's (likely) heterogeneity, i.e., the differences in computing power of its constituent workstations. Initial studies have led to a mathematical framework for the proposed research.Technical impact.. The proposed work will provide rigorously validated guidelines forscheduling a broad variety of significant computational problems efficiently on heterogeneous clusters. Research results will be disseminated in leading conferences and journals, and will beincorporated into courses and seminars. Via the training of students, and via collaborations and technical interactions with colleagues, both in the US and abroad, the work will lead to yet further technical progress. (There are ongoing collaborations with colleagues in Australia, France, and Italy.)Broader impacts. Prior support from NSF has led to the incorporation of cutting-edgetechnical material into independent studies, courses, and research seminars, which have been part of the training of several generations of students in several departments at U Mass Amherst. All but one of the PI's doctoral students have pursued (successful) academic careers at colleges or universities in the US. Two recent doctoral students have been women: one was born in China and one in eastern Europe; both are successfully pursuing careers in US educational institutions.Results from the proposed research will be incorporated into the educational program in the same way that prior results have been.