Evolutionary Model of Optimization of Modular Associative Memory for Dataflow Machines Based on Genetic Algorithm

An evolutionary model of modular associative memory for machines with dataflow architecture is suggested. A problem of determination of optimal allocation of a dataflow in a computational system with modular associative memory is formulated. The model suggested is based on graph representation of the dataflow. The allocation of the dataflow among modules is realized by means of a hash function. A method for searching for optimal hashing with the use of a genetic algorithm is suggested. The convergence of the genetic algorithm is studied. Estimates of optimal allocation among modules of associative memory for various computational problems are obtained.     

Heavy traffic optimal resource allocation algorithms for cloud computing clusters

Cloud computing is emerging as an important platform for business, personal and mobile computing applications. In this paper, we study a stochastic model of cloud computing, where jobs arrive according to a stochastic process and request resources like CPU, memory and storage space. We consider a model where the resource allocation problem can be separated into a routing or load balancing problem and a scheduling problem. We study the join-the-shortest-queue routing and power-of-two-choices routing algorithms with the MaxWeight scheduling algorithm. It was known that these algorithms are throughput optimal. In this paper, we show that these algorithms are queue length optimal in the heavy traffic limit.     

F1owS:一种MapReduce数据流公平调度方法

MapReduce Job的调度机制一直是学术研究的热点。在分析MapReduce数据流调度模型的基础上,提出一种面向MapReduce数据流的公平调度方法FlowS。该方法采用数据流池来分配资源以保证MapReduce数据流的隔离性,并且采用数据流池动态构建算法来确保资源的公平分配。实验表明,该调度方法可以有效提高Hadoop集群对MapReduce数据流的处理效率。     

改进的资源优化分配调度方法研究

资源优化分配和调度是一个传统的研究问题,目前在实际工程应用中,通常是以最小费用为目标,建立最优化的线性规划模型,但在多变量多参数约束的条件下,优化调度模型往往求解困难,甚至无解。以渠道土石方调配为例子,研究基于南水北调山东段100多公里的渠道土石方优化调度系统,提出了一个基于最近距离优先的土石方优化调度算法,该算法通过搜索所有相同最近的分段进行土石方调度,以实现最小费用优先的目标。最后通过实例论证了该算法的有效性,研究成果对相关类似的资源优化调度和分配研究具有重要的参考价值。     

Design and analysis of a class-aware recursive loop scheduler for class-based scheduling

In this paper, we consider the problem of devising a loop scheduler that allocates slots to users according to their relative weights as smoothly as possible. Instead of the existing notion of smoothness based on balancedness, we propose a variance-based metric which is more intuitive and easier to compute.We propose a recursive loop scheduler for a class-based scheduling scenario based on an optimal weighted round-robin scheduler. We show that it achieves very good allocation smoothness with almost no degradation in intra-class fairness. In addition, we also demonstrate the equivalence between our proposed metric and the balancedness-based metric.     

基于高地址约束和按需存储分配的UCard底层调度模块研究

本文介绍了一种实现一卡多发的新型智能卡UCard及其体系结构。针对UCard现有固定存储空间分配存在资源浪费等不足,提出了一种按需存储空间分配方法,并且该方法通过对高位地址总线的约束实现了不同大小COS之间的物理隔离。然后在引入动态地址控制器的基础上,给出了基于按需存储空间分配的UCard底层调度模块的一种实现方式。最后利用有限状态机对UCard底层调度模块装载、调度、卸载COS的过程进行了形式化描述。     

Communication storage optimization for static dataflow with access patterns under periodic scheduling and throughput constraint

We address a recently introduced static dataflow model: the Static Dataflow with Access Patterns (SDF-AP) model. For this model we present (1) a generalization of an existing regular periodic scheduling scheme to regular 1-periodic scheduling for flexibility to achieve a smaller schedule period and additional room for optimization on communication storage; (2) a method based on Integer Linear Programming (ILP) to minimize communication buffers under periodic scheduling and user-specified throughput constraints. Experimental results on a set of test cases show that buffer sizes using this approach can be reduced dramatically when compared to the traditional SDF models. The optimal sizing result may serve as an important criterion to evaluate and fine-tune any heuristics-based buffer sizing approach for the SDF-AP model of computation.     

The Dataflow Time and Space Complexity of FFTs

In this paper we analyze the performance of a recursive and an iterative fast Fourier transform algorithm, written in Id and run on MINT, a simulator for the Monsoon dataflow machine. Our complexity measures are: the number of instructions executed, the critical path length of the dataflow graph, and the storage occupancy. Using a set of simple functions, we calibrate loop and divide-and-conquer behavior of Monsoon and compare it with the "tagged token dataflow architecture." We discuss the issues in explicit resource management in a functional language, introduce the language features required for this, and show results of our resource managed FFT programs.     

Two-machine no-wait flowshop scheduling with learning effect and convex resource-dependent processing times

Two-machine no-wait flowshop scheduling problems in which the processing time of a job is a function of its position in the sequence and its resource allocation are considered in the study. The primary objective is to find the optimal sequence of jobs and the optimal resource allocation separately. Here we propose two separate models: minimizing a cost function of makespan, total completion time, total absolute differences in completion times and total resource cost; minimizing a cost function of makespan, total waiting time, total absolute differences in waiting times and total resource cost. Since each model is strongly NP-hard, we solve both models by breaking them down to two sub-problems, the optimal resource allocation problem for any job sequence and the optimal sequence problem with its optimal resource allocation. Specially, we transform the second sub-problem into the minimum of the bipartite graph optimal matching problem (NP-hard), and solve it by using the classic KM (Kuhn–Munkres) algorithm. The solutions of the two sub-problems demonstrate that the target problems remain polynomial solvable under the proposed model.     

树型网格计算环境下的独立任务调度

任务调度是实现高性能网格计算的一个基本问题,然而,设计和实现高效的调度算法是非常具有挑战性的.讨论了在网格资源计算能力和网络通信速度异构的树型计算网格环境下,独立任务的调度问题.与实现最小化任务总的执行时间不同(该问题已被证明是NP难题),为该任务调度问题建立了整数线性规划模型,并从该线性规划模型中得到最优任务分配方案??各计算节点最优任务分配数.然后,基于最优任务分配方案,构造了两种动态的需求驱动的任务分配启发式算法:OPCHATA(optimization-based priority-computation heuristic algorithm for task allocation)和OPBHATA(optimization-basedpriority-bandwidth heuristic algorithm for task allocation).实验结果表明:在异构的树型计算网格环境下实现大量独立任务调度时,该算法的性能明显优于其他算法.     

Using Timed Petri Net to Model Instruction-Level Loop Scheduling with Resource Constraints

This paper uses timed petri net to model and analyze the problem of instructionlevel loop scheduling with resource constraints,which has been proven to be an NP complete problem.First,we present a new timed Petri net model to integrate functional unit allocation,register allocation and spilling into a unified theoretical framework.Then we develop a state subgraph,called Register Allocation Solution Graph,which can effectively describe the major behavior of our new model.the main property of this state subgraph is that the number of all its nodes is polynomial.Finally we present and prove that the optimum loop schedules can be found with polynomial computation complexity,for almost all practical loop programs.Our work lightens a new idea of finding the optimum loop schedules.     

一种基于QoS的自适应网格失效检测器

失效检测器是构建可靠的网格计算环境所必需的基础组件之一.由于网格中存在大量对失效检测有着不同QoS需求的分布式应用,对于一个网格失效检测器来说,为保持其有效性和可扩展性,应该既能够准确提供应用程序所需的失效检测QoS,又能够避免为满足不同QoS而设计多套失效检测器所产生的多余负载.基于QoS基本评价指标,采用PULL模式主动检测策略实现了一种新的失效检测器--GA-FD(adaptive failure detector for grid),可以同时支持多个应用程序定量描述的QoS需求,不需要关于消息行为和时钟同步的任何假设.同时,证明了GA-FD在部分同步模型下可实现一个◇P类的失效检测器,并给出了相应的实验及数据.     

Data dependent loop scheduling based on genetic algorithms for distributed and shared memory systems

Many approaches have been described for the parallel loop scheduling problem for shared-memory systems, but little work has been done on the data-dependent loop scheduling problem (nested loops with loop carried dependencies). In this paper, we propose a general model for the data-dependent loop scheduling problem on distributed as well as shared memory systems. In order to achieve load balancing and low runtime scheduling and communication overhead, our model is based on a loop task graph and the notion of critical path. In addition, we develop a heuristic algorithm based on our model and on genetic algorithms to test the reliability of the model. We test our approach on different scenarios and benchmarks. The results are very encouraging and suggest a future parallel compiler implementation based on our model.     

Integrated well pad development scheduling with steam injection control in steam-assisted gravity drainage

In this paper, we study the problem of integrated well pad development scheduling with nonlinear model predictive control based steam injection in steam-assisted gravity drainage (SAGD). The scheduling problem has been modeled as a mixed-integer program to find optimal development sequence and timing of multiple well-pads. Model predictive control problems are solved to find optimal steam injection profile such that the reservoir is under control. The integrated problem is solved using open-loop and closed-loop methods: (1) scheduling problem is only solved at the beginning of project operation, (2) Scheduling problem is solved every year with shrinking horizon implementation, and (3) shrinking horizon implementation of scheduling with reservoir model update based on feedback from control level. Simulation results demonstrate the benefits of closed-loop integrated scheduling and control: the NPV increase is 19%.     

考虑非确定加工时间的柔性作业车间调度问题研究

加工时间不确定的柔性作业车间调度问题已逐渐成为生产调度研究的热点。采用区间表示加工时间范围,利用时间Petri网建立区间柔性作业车间调度问题形式化模型,并运用网模型的状态类图进行可达性分析,计算出所有可行变迁触发序列。通过对触发序列的时序分析,提出一种有效的逆向分步法来构造触发序列的时间约束不等式,进而求解线性规划问题来获得最小完工时间下界(上界)的优化调度策略。最后利用实例分析验证了模型及所提方法的正确性和可行性,为实际的区间柔性作业车间调度问题提供有效方案。     

Compiler-assisted leakage-aware loop scheduling for embedded VLIW DSP processors

As feature size shrinks, leakage energy consumption has become an important concern. In this paper, we develop a compiler-assisted instruction-level scheduling technique to reduce leakage energy consumption for applications with loops on VLIW architecture. In the proposed technique, we obtain the schedule with minimum leakage energy from the ones that are generated by repeatedly regrouping a loop based on rotation scheduling and bipartite-matching. We conduct experiments on a set of benchmarks from DSPstone, Mediabench, Netbench, and MiBench based on the power model of the VLIW processors. The results show that our algorithm can achieve significant leakage energy saving compared with the previous work.     

考虑机器检修的热轧钢管批量计划方法

本文从无缝钢管生产实际中提取并定义了周期性机器检修环境下的钢管热轧批量计划问题,基于无缝钢管生产的特殊性,将该问题抽象为一类考虑机器检修和机器调整时间的单机调度问题,并建立了以最小化机器闲置和机器调整时间为目标的数学模型.针对批量间的机器调整时间取决于钢管规格的变化这一特性,提出了最小调整时间排序规则,证明了该规则在不考虑检修计划时具有最优性.进而,以此为基础建立了循环求解框架,并设计了两阶段启发式算法.基于实际生产数据设计了多种问题规模的实验,验证了算法的有效性,并从实际应用角度对结果进行了分析.     

A Pipelining Loop Optimization Method for Dataflow Architecture

与 exascale 来超级计算的时代,电源效率成为了最重要的障碍造一个 exascale 系统。Dataflow 建筑学在为科学应用完成高电源效率有本国的优点。然而,最先进的 dataflow 体系结构没能为循环处理利用高并行。处理这个问题,我们建议一个 pipelining 环优化方法(PLO ) ,它在处理元素(PE ) 在环流动做重复 dataflow 的数组加速器。这个方法由二种技术,帮助建筑学的硬件重复和帮助说明的软件重复组成。在硬件重复执行模型,一个在薄片上循环控制器被设计产生循环索引,减少计算内核并且打为 pipelining 执行的一个好基础的复杂性。在软件重复实行模型,另外的环指令被论述解决重复相关性问题。经由这二种技术,准备好了每周期执行的指令的平均数字被增加使浮点联合起来忙。当这二种技术的硬件费用是可接受的时,模拟结果证明分别地,我们的建议方法平均由 2.45x 和 1.1x 在浮点效率超过静电干扰和动态循环执行模型。     

Static Scheduling of Conditional Branches in Parallel Programs

The problem of scheduling non-deterministic graphs arises in several situations in scheduling parallel programs, particularly in the cases of loops and conditional branching. When scheduling loops in a parallel program, non-determinism arises because the number of loop iterations may not be known before the execution of the program. However, since loops from a restricted class of conditional branching, there is a higher degree of non-determinism associated with scheduling conditional branching. In this case, the direction of every branch remains unknown before run time. It follows that entire subprograms of the parallel program may or may not get executed, which in turn increases the amount of non-determinism and complicates the scheduling process. Thus, the term non-determinism is frequently associated with conditional branching in the literature. In this paper, we study the problem of constructing a static schedule for task graphs that contain conditional branching on parallel computers. Generally, it is difficult to obtain optimal solutions for solving various scheduling problems, even in the deterministic case. When non-determinism is added to the scheduling problem through conditional branching, an optimal solution will be even harder to obtain. We start the paper with a brief discussion of the scheduling problem, then we introduce a model for representing parallel programs that contain branches. We present a two-step scheduling technique which employs two different approaches: a graph theoretic appraoch and a multi-phase approach. The first approach is based on exploring several graph theoretic properties of the model. This approach is used as a preprocessing step to decrease the amount of non-determinism before applying the multi-phase approach. In the second step, several execution instances of the program are generated, a schedule for every instance is obtained, and a unified schedule is constructed by merging the obtained schedules. Finally, we report the results of the experiments that we conducted to measure the performance of the techniques introduced in this paper.