As the gap between compute and I/O performance tends to grow, modern High-Performance Computing (HPC) architectures include a new resource type: an intermediate persistent fast memory layer, called burst buffers. This is just one of many kinds of renewable resources which are orthogonal to the processors themselves, such as network bandwidth or software licenses. Ignoring orthogonal resources while making scheduling decisions just for processors may lead to unplanned delays of jobs of which resource requirements cannot be immediately satisfied. We focus on a classic problem of makespan minimization for parallel-machine scheduling of independent sequential jobs with additional requirements on the amount of a single renewable orthogonal resource. We present an easily-implementable log-linear algorithm that we prove is $2\frac56$-approximation. In simulation experiments, we compare our algorithm to standard greedy list-scheduling heuristics and show that, compared to LPT, resource-based algorithms generate significantly shorter schedules.
翻译:随着计算与I/O性能之间的差距日益扩大,现代高性能计算(HPC)结构包括一种新的资源类型:中间的持久性快速内存层,称为防爆缓冲层。这只是对处理者本身具有正正反的多种可再生资源之一,例如网络带宽或软件许可。当仅为处理者做出时间安排时,忽略正反资源可能导致工作意外延误,而资源需求无法立即得到满足。我们集中关注一个典型的问题,即对独立的连续连续工作的平行机器排班进行最小化,同时对单一可再生或远方资源的数量提出额外要求。我们提出了一个易于执行的日志线算法,我们证明这种算法是2\frac56$-appronomication。在模拟实验中,我们将我们的算法与标准的贪婪列表安排外观作比较,并表明,与LPT相比,基于资源的算法的算法会产生大大短的时间表。