Scheduling Collaborative Computations on Heterogeneous Clusters

在过去的十年里，用于各种计算的计算平台发生了范式的转变。技术和经济方面的进步已使工作站或PC集群成为高性能“协作”计算(其中多台计算机协作以解决单个计算问题)的可行媒介。许多在早期计算环境中确保高效“协作”计算的算法设备不再保证在这样的集群内的效率，特别是当集群是异类的时候，因为它们的工作站在计算能力上可能不同。本文提出的研究计划致力于通过针对大类重要计算的高效算法，在异类集群中实现被证明有效的计算。“可证明有效的计算”目标的第一个组成部分将是使用分析和实验方法相结合的方法来开发制定调度算法所需的洞察力，这些算法的性能可以通过严格的数学和/或统计分析进行预测。目标的第二个组成部分将是验证用于制定和分析算法的抽象模型。在实际集群上实施算法，并将测量的性能与抽象算法模型的预测进行比较，将用于验证或在必要时修改模型。这一过程产生的调度算法及其适当的实现将是该研究的主要成果。拟议的研究将集中在通过局域网互连的由现成的工作站或PC组装而成的“特别”集群。这里的主要调度挑战在于工作站间通信的巨大成本以及集群的(可能)异构性，即其组成工作站的计算能力的差异。初步研究已经为拟议的研究形成了一个数学框架。所提出的工作将为在异类集群上高效地调度各种重要的计算问题提供经过严格验证的指导方针。研究成果将在主要会议和期刊上传播，并将被纳入课程和研讨会。通过对学生的培训，以及与国内外同事的合作和技术互动，这项工作将带来进一步的技术进步。(与澳大利亚、法国和意大利的同事正在进行合作。)更广泛的影响。NSF先前的支持导致将尖端技术材料纳入独立研究、课程和研究研讨会，这些都是麻省理工学院几个系几代学生培训的一部分。除一名外，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.