A Proposal to Extend the OpenMP Tasking Model with Dependent Tasks

Tasking in OpenMP 3.0 has been conceived to handle the dynamic generation of unstructured parallelism. New directives have been added allowing the user to identify units of independent work (tasks) and to define points to wait for the completion of tasks (task barriers). In this document we propose extensions to allow the runtime detection of dependencies between generated tasks, broading the range of applications that can benefit from tasking or improving the performance when load balancing or locality are critical issues for performance. The proposed extensions are evaluated on a SGI Altix multiprocessor architecture using a couple of small applications and a prototype runtime system implementation.     

Two-sided assembly line balancing considering the relationships between tasks

Previous studies of the two-sided assembly line balancing problem assumed equal relationships between each two tasks assignable to a side of the line. In practice, however, this relationship may be related to such factors as the distance between the implementation place and the tools required for implementation. We know that the more relationships exist between the tasks assigned to each station, the more efficient will be the assembly line. In this paper, we suggest an index for calculating the value of the relationship between each two tasks, and define a performance criterion called ‘assembly line tasks consistency’ for calculating the average relationship between the tasks assigned to the stations of each solution. We propose a simulated annealing algorithm for solving the two-sided assembly line balancing problem considering the three performance criteria of number of stations, number of mated-stations, and assembly line tasks consistency. Also, the simulated annealing algorithm is modified for solving the two-sided assembly line balancing problem without considering the relationships between tasks. This modification finds five new best solutions for the number of stations performance criterion and ten new best solutions for the number of mated-stations performance criterion for benchmark instances.     

基于Linux的实时操作系统的分析与研究

本文讨论了实时操作系统的现状及标准Linux作为实时应用的一些不足,并从实现机制上分析了造成这些不足的原因,在此基础上,深入分析了现有的实时Linux操作系统的特性和设计实现原理,并对进一步的工作提出了展望。     

Efficient implementation of tight response-times for tasks with offsets

Earlier approximate response time analysis (RTA) methods for tasks with offsets (transactional task model) exhibit two major deficiencies: (i) They overestimate the calculated response times resulting in an overly pessimistic result. (ii) They suffer from time complexity problems resulting in an RTA method that may not be applicable in practice. This paper shows how these two problems can be alleviated and combined in one single fast-and-tight RTA method that combines the best of worlds, high precision response times and a fast approximate RTA method. Simulation studies, on randomly generated task sets, show that the response time improvement is significant, typically about 15% tighter response times in 50% of the cases, resulting in about 12% higher admission probability for low priority tasks subjected to admission control. Simulation studies also show that speedups of more than two orders of magnitude, for realistically sized tasks sets, compared to earlier RTA analysis techniques, can be obtained. Other improvements such as Palencia Gutiérrez, González Harbour (Proceedings of the 20th IEEE real-time systems symposium (RTSS), pp. 328–339, 1999), Redell (Technical Report TRITA-MMK 2003:4, Dept. of Machine Design, KTH, 2003) are orthogonal and complementary which means that our method can easily be incorporated also in those methods. Hence, we conclude that the fast-and-tight RTA method presented is the preferred analysis technique when tight response-time estimates are needed, and that we do not need to sacrifice precision for analysis speed; both are obtained with one single method.

A two-stage heuristic for multi-activity and task assignment to work shifts

The multi-activity assignment problem consists of assigning interruptible activities to given work shifts so as to match as much as possible for each activity a demand curve in function of time. In this paper we consider an extension to this problem, called the multi-activity and task assignment problem, that additionally considers the assignment of uninterruptible pieces of work, called tasks. These possess properties such as worker qualifications, time windows for completion, fixed lengths and precedence relationships. We propose a mixed-integer programming formulation and a two-stage method to solve this problem. The first stage consists of an approximation mixed-integer programming model to assign tasks approximately taking into account the activities and the second involves a column generation heuristic for assigning activities and reassigning tasks at the same time. We suggest four different strategies for reassigning tasks. We conducted extensive computational tests on randomly generated instances in order to validate our method and to compare the various strategies. One strategy proved universally best when compared to the other three policies.     

Analysis of multiple activity manual materials handling tasks using A Guide to Manual Materials Handling

Manual handling of materials continues to be a hazardous activity, leading to a very significant number of severe overexertion injuries. Designing jobs that are within the physical capabilities of workers is one approach ergonomists have adopted to redress this problem. As a result, several job design procedures have been developed over the years. However, these procedures are limited to designing or evaluating only pure lifting jobs or only the lifting aspect of a materials handling job. This paper describes a general procedure that may be used to design or analyse materials handling jobs that involve several different kinds of activities (e.g. lifting, lowering, carrying, pushing, etc). The job design/analysis procedure utilizes an elemental approach (breaking the job into elements) and relies on databases provided in A Guide to Manual Materials Handling to compute associated risk factors. The use of the procedure is demonstrated with the help of two case studies.     

A comparative study of task communication in ada

A previous paper compared the mechanisms for process communication in Hoare's communicating sequential processes and in Brinch Hansen's distributed processes, by both qualitative and quantitative analyses. This paper extends these analyses to the corresponding features for communication between tasks in Ada. The similarity between Ada's features and Hoare's proposals is confirmed, but some limitations on non-determinism in Ada are noted.     

在对阻力的预期判断中进行规划

当自下而上的规划占据主流地位时，上层政府机构尽管忽视了舟共部门规划但仍保留针对发展的批评制度机制。在援引了新工业化国家为城市贫民提供住房和就业问题的例子后．文章阐述了在一个有效规划中，规划的本体论和程序论是不能相互分离的，因为规划程序很大程度被其欲解决的特定问题的本质所左右。因此，规划理论家需要甘问题的本质有更好的认识，以便为规划操作者提供制度上的洞察力，以应对当问题以特殊方式被提出时可能会遇到的阻力。     

面向制造协作联盟的时序约束制造任务跨度研究

针对协作制造联盟的制造任务,分析了制造任务规划与制造资源配置之间的关系,建立了时序约束制造任务跨度模型.从制造任务协作成本、生产周期与任务分解方案3个方面出发,定性、定量地分析了影响时序约束制造任务跨度规划的问题,建立了影响因素与任务跨度之间的数学关系式,得出了最优的任务跨度值.从这些拟定量分析的结果出发,得出一些有益于协作制造任务规划的结论.     

以策略为机制的网格任务调度模型研究

针对网格调度在网格中的重要性,提出了一种以策略为机制的网格任务调度模型。解释了模型中各功能部件的作用及其相互之间的关系,给出了与模型相对应的进行任务调度所需要的算法伪码。用Gridsim仿真工具验证模型的可实施性。