Shared processor scheduling

We study the shared processor scheduling problem with a single shared processor to maximize total weighted overlap, where an overlap for a job is the amount of time it is processed on its private and shared processor in parallel. A polynomial-time optimization algorithm has been given for the problem with equal weights in the literature. This paper extends that result by showing an \(O(n \log n)\)-time optimization algorithm for a class of instances in which non-decreasing order of jobs with respect to processing times provides a non-increasing order with respect to weights—this instance generalizes the unweighted case of the problem. This algorithm also leads to a \(\frac{1}{2}\)-approximation algorithm for the general weighted problem. The complexity of the weighted problem remains open.     

Efficient scheduling of tasks without full use of processor resources

The nonpreemptive scheduling of a partially ordered set of tasks on a machine with m processors of different speeds is studied. Polynomial time algorithms are presented which benefit from selective non-use of slow processors. The performance of these heuristics is asymptotic to √m times worse than optimal, whereas list schedules are unboundedly worse than optimal for any fixed value of m. The techniques of analyzing these schedules are used to obtain a bound on a large class of preemptive schedules.     

Instruction scheduling and transformation for a VLIW unified reduced instruction set computer/digital signal processor processor with shared register architecture

The popularity of multimedia applications made them a major theme in embedded systems. The key component for supporting multimedia application well is embedded processor. Thus, we have designed and implemented an embedded processor, called UniDual processor, to achieve this objective. Its key features are the integration of instructions of reduced instruction set computers (RISCs) and digital signal processors (DSPs) as well as the support of special instruction set and shared‐based clustered register architecture. However, an important issue of UniDual that remains open is how to efficiently allocate registers. In this paper, we present a scheduling and instruction transformation approach to resolve the aforementioned issue. The proposed approach schedules instructions and then transforms overlapped instructions into RISC and DSP instructions by taking communication overhead and hardware limitations into account. Compared with the greedy approach, the evaluation shows that our work is relatively effective in performance and code size reduction. Copyright © 2012 John Wiley & Sons, Ltd.     

Two processor scheduling with limited preemption

We introduce deterministic task system scheduling with limited preemption—that is, a preempted task can resume execution only on the processor where it originally executed. Two classes of limited preemptive schedules are introduced, corresponding to whether or not unforced idle time is allowed in the schedule. Our main result is to show that, on two processors, these two classes are equivalent with respect to optimal schedule lengths. We use this result to establish a hierarchy of optimal schedule lengths.     

3D graphics processor chip set

Increasingly, 3D graphics is becoming the rule rather than the exception in applications such as games, CAD/CAM, and video production. Some LSIs provide rendering capabilities, but require an additional CPU to perform essential geometry transformations. Fujitsu's chip set solves that problem using two processors to render 300,000 polygons per second (for flat-shaded triangles with texture)-performance comparable to that of advanced game machines     

Using processor affinity in loop scheduling on shared-memorymultiprocessors

Loops are the single largest source of parallelism in many applications. One way to exploit this parallelism is to execute loop iterations in parallel on different processors. Previous approaches to loop scheduling attempted to achieve the minimum completion time by distributing the workload as evenly as possible while minimizing the number of synchronization operations required. The authors consider a third dimension to the problem of loop scheduling on shared-memory multiprocessors: communication overhead caused by accesses to nonlocal data. They show that traditional algorithms for loop scheduling, which ignore the location of data when assigning iterations to processors, incur a significant performance penalty on modern shared-memory multiprocessors. They propose a new loop scheduling algorithm that attempts to simultaneously balance the workload, minimize synchronization, and co-locate loop iterations with the necessary data. They compare the performance of this new algorithm to other known algorithms by using five representative kernel programs on a Silicon Graphics multiprocessor workstation, a BBN Butterfly, a Sequent Symmetry, and a KSR-1, and show that the new algorithm offers substantial performance improvements, up to a factor of 4 in some cases. The authors conclude that loop scheduling algorithms for shared-memory multiprocessors cannot afford to ignore the location of data, particularly in light of the increasing disparity between processor and memory speeds     

Modelling heterogeneous processor scheduling for real-time systems

A new model is presented to describe data-flow algorithms implemented in a multiprocessing system. Called the resource/data flow graph (RDFG), the model explicitly represents cyclo-static processor schedules as circuits of processor arcs that reflect the order that processors execute graph nodes. The model also allows the guarantee of meeting hard real-time deadlines. When unfolded, the model identifies statistically the processor schedule. The model therefore is useful for determining the throughput and latency of systems with heterogeneous processors. The applicability of the model is demonstrated using a space surveillance algorithm.     

异构多核处理器的任务调度算法

在研究Min-min、Max-min算法和Sufferage算法基础上,针对异构多核处理器的特点,提出一种任务静态调度算法——自适应分段Sufferage算法（Adaptive Segmented Sufferage,ASS）。该算法以最早完成时间和负载均衡为目标进行任务分配,先将任务分配分成两个阶段：在第一个阶段以最少完成时间作为分配原则进行分配,选择单位时间内节省时间最多的任务先分配;在第二个阶段以负载均衡为分配原则进行分配,选择执行时间大的任务先分配。然后选取不同调节参数,对任务进行多次重新分配,以最小的最大完成时间为最后分配结果,实现自适应调节。通过实验验证,该算法在实现最少完成时间的前提下能很好地达到负载均衡。     

Two-level utilization-based processor allocation for scheduling moldable jobs

The Journal of Supercomputing - Most modern parallel programs are written with the moldable property. However, most existing parallel computing systems treat such parallel programs as rigid jobs...     

基于时间帧的处理器PFair调度改进算法

为了解决PFair算法进行交互任务调度时,由于忽略了不同阶段的周期性任务而导致多个线程之间任务的迁移问题以及空间和时间的浪费问题,提出了基于时间帧的处理器PFair调度改进算法。该算法基于周期性任务系统的特点,引入时间帧控制和改变本地周期性任务调度来限制任务迁移,从而实现对PFair算法的改进。为了评估算法的迁移开销和公平性,通过实验对普通PFair算法及本文所提出的改进算法ERfair进行对比实验,结果表明,改进算法ERfair能够通过时间帧内调度和分区控制大大降低任务在不同处理器间的迁移次数。基于时间帧的处理器PFair调度改进算法在保证公平性的同时,提高了系统的效率,应用于多核处理器上的任务调度是可行的、有效的。     

一种面向VLIW芯片的线性指令调度算法

VLIW是DSP芯片上使用最多的一种技术,要发挥DSP芯片的性能优势,需要编译器的支持.目前关于VLLW技术的研究主要集中在如何形成更长的基本块,以及基本块之间的代码优化算法上,对于如何选择指令从而形成一个超长指令字的算法,却没有仔细地描述和实现,但这是在编译器的指令调度模块中需要具体考虑的问题,具有工程实践意义.本文通过改进编译器的lisf算法实现了支持VLIW技术的指令调度优化算法,改进的算法可以充分利用芯片的VLIW结构的优势,加速程序运行,具有较好性能.     

专用指令集处理器(ASIP)评估方法研究

针对专用指令集处理器(ASIP)评估具有多属性维数、多目标类型、多数据类型的特点,提出一种基于比较的评估方法.在评估的不同阶段,选取不同的参照指标,对数据进行处理、集结,从而获取候选方案的排序向量.根据评估目标类型和数据信息类型选取特定的参照数据,进行数据信息与参照数据的比较;利用模糊矩阵对评估指标的重要程度进行两两比较,并对其进行一致性判断和修正,获取指标权值向量;最后,利用有序加权平均法获取各候选方案的综合属性值,并提出区间比较度的概念,为评估提供量化依据.实例计算表明了该方法的有效性.     

Job scheduling and processor allocation for grid computing on metacomputers

Scheduling is a fundamental issue in achieving high performance on metacomputers and computational grids. For the first time, the job scheduling problem for grid computing on metacomputers is studied as a combinatorial optimization problem. A cost model is proposed for modeling communication heterogeneity on computational grids. A processor allocation algorithm is developed which always finds an optimal processor allocation that minimizes the effective execution time of a job when the job is being scheduled. It is proven that the list scheduling (LS) algorithm can achieve reasonable worst-case performance bound in grid environments supporting distributed supercomputing with large applications. We compare the performance of various job scheduling and processor allocation algorithms for grid computing on metacomputers. We evaluate the performance of 128 combinations of two job scheduling algorithms, four initial job ordering strategies, four processor allocation algorithms, and four metacomputers by extensive simulation. It is found that the combination of largest job first (LJF) initial job ordering and minimum effective execution time (MEET) or largest machine first (LMF) processor allocation algorithm yields the best average-case performance, and the choice of FCFS and LS depends on the range of job sizes. It is also observed that communication heterogeneity does have significant impact on schedule lengths.     

Variable assignment and instruction scheduling for processor with multi-module memory

Multi-module memory has been employed in high-end digital signal processing system (DSP). It provides high memory bandwidth and low power operating mode for energy savings. However, making full use of these architectural features is a challenging problem for code optimization. In this paper, we propose an integer linear programming (ILP) model to optimize the performance and energy consumption of multi-module memories by solving variable assignment, instruction scheduling and operating mode setting problems simultaneously. The combined effect of performance and energy saving requirements has been considered as well. Specially, we develop two optimization techniques to improve the computation efficiency of our ILP model. The experimental results show that the optimal performance and energy solution can be achieved within a reasonable amount of time.     

Ray-driven dynamic working set rendering

Ray tracing a volume scene graph composed of multiple point-based volume objects (PBVO) can produce high quality images with effects such as shadows and constructive operations. A naive approach, however, would demand an overwhelming amount of memory to accommodate all point datasets and their associated control structures such as octrees. This paper describes an out-of-core approach for rendering such a scene graph in a scalable manner. In order to address the difficulty in pre-determining the order of data caching, we introduce a technique based on a dynamic, in-core working set. We present a ray-driven algorithm for predicting the working set automatically. This allows both the data and the control structures required for ray tracing to be dynamically pre-fetched according to access patterns determined based on captured knowledge of ray-data intersection. We have conducted a series of experiments on the scalability of the technique using working sets and datasets of different sizes. With the aid of both qualitative and quantitative analysis, we demonstrate that this approach allows the rendering of multiple large PBVOs in a volume scene graph to be performed on desktop computers.     

Characterizing and reproducing working set size dynamics

A characterization of program referencing dynamics based on the temporal behavior of memory demand (as represented by the working set size of a program for a given window size) is proposed. A deterministic generative model which produces a references string having a given dynamic characterization is then presented, and its practical implementation is discussed. An experimental study of the accuracy and the viability of such a model is performed, together with a theoretical and empirical investigation of the feasibility of constructing a synthetic program which produces an approximation to that artificial string, thereby exhibiting the given dynamic behavior. The results for working-set-like environments with window sizes larger than or equal to that used in the generation of the artificial string are satisfactory, but those for other types of memory policies reveal that improvements to the string generation algorithm or different characterizations are needed.     

Genetic scheduling for parallel processor systems: comparativestudies and performance issues

Task scheduling is essential for the proper functioning of parallel processor systems. Scheduling of tasks onto networks of parallel processors is an interesting problem that is well-defined and documented in the literature. However, most of the available techniques are based on heuristics that solve certain instances of the scheduling problem very efficiently and in reasonable amounts of time. This paper investigates an alternative paradigm, based on genetic algorithms, to efficiently solve the scheduling problem without the need to apply any restricted assumptions that are problem-specific, such is the case when using heuristics. Genetic algorithms are powerful search techniques based on the principles of evolution and natural selection. The performance of the genetic approach will be compared to the well-known list scheduling heuristics. The conditions under which a genetic algorithm performs best will also be highlighted. This will be accompanied by a number of examples and case studies     

Fuzzy reasoning based on a new fuzzy rough set and its application to scheduling problems

In this paper, we study the fuzzy reasoning based on a new fuzzy rough set. First, we define a broad family of new lower and upper approximation operators of fuzzy sets between different universes using a set of axioms. Then, based on the approximation operators above, we propose the fuzzy reasoning based on the new fuzzy rough set. By means of the above fuzzy reasoning based on the new fuzzy rough set, for a given premise, we can obtain the fuzzy reasoning consequence expressed by the fuzzy interval constructed by the above two approximations of fuzzy sets. Furthermore, through the defuzzification of the lower and upper approximations, we can get the corresponding two values constructing the interval used as the fuzzy reasoning consequence after defuzzification. Then, from the above interval, a suitable value can be selected as the final reasoning consequence so that some special constraints are satisfied as possibly. At last, we apply the fuzzy reasoning based on the new fuzzy rough set to the scheduling problems, and numerical computational results show that the fuzzy reasoning based on the new fuzzy rough set is more suitable for the scheduling problems compared with the fuzzy reasoning based on the CRI method and the III method.