Scheduling Collaborative Computations on Heterogeneous Clusters

Rosenberg，Aronld马萨诸塞州大学AmherstCCF-0342417过去十年，用于各种计算的计算平台发生了范式转变。 技术的进步和经济的考虑使得工作站集群或pc成为高性能“协作”计算（其中许多计算机协作解决单个计算问题）的可行介质。 在早期的计算环境中确保有效的“协作”计算的许多算法设备不再保证这样的集群内的效率，特别是当集群是异构的时，在这个意义上，它们的工作站可能在计算能力上不同。 本文提出的研究方案致力于通过大类重要计算的高效算法，在异构集群中实现可证明的高效计算。 “可证明有效的计算”目标的第一个组成部分将是使用分析和实验方法的组合来开发所需的见解，以制定调度算法，其性能可以通过严格的数学和/或统计分析来预测。 目标的第二个组成部分是验证用于制定和分析算法的抽象模型。 算法在实际集群上的实现，以及测量性能与抽象算法模型预测的比较，将用于验证或在必要时修改模型。 调度算法，并在适当的情况下，实现其结果，从这个过程中将是主要的products.The拟议的研究将集中在“广告”集群，这是组装从“现成的”工作站或个人电脑的，通过局域网互连。 这里的主要调度挑战在于工作站间通信的大量成本和集群的（可能的）异构性，即，其组成工作站的计算能力的差异。 初步研究已经为拟议的研究提供了一个数学框架。所提出的工作将提供严格验证的准则forscheduling各种各样的重要的计算问题，有效地异构集群。 研究成果将在主要会议和期刊上传播，并将纳入课程和研讨会。 通过对学生的培训，以及与美国和国外同事的合作和技术互动，这项工作将导致进一步的技术进步。 （与澳大利亚、法国和意大利的同事正在进行合作。）更广泛的影响。 从NSF先前的支持导致了cutting-edgetechnical材料纳入独立的研究，课程和研究研讨会，这一直是几代学生在几个部门在U马萨诸塞州阿默斯特培训的一部分。 除了一名博士生外，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.