检索结果-内蒙古大学图书馆

Scheduling data-flow graphs via retiming and unfolding

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 1997年第12期8卷 1259-1267页

作者： Chao, LF Sha, EHM Iowa State Univ Dept Elect & Comp Engn Ames IA 50011 USA Univ Notre Dame Dept Comp Sci & Engn Notre Dame IN 46556 USA

Loop scheduling is an important problem in parallel processing. The retiming technique reorganizes an iteration;the unfolding technique schedules several iterations together. We combine these two techniques to obtain a static schedule with a reduced average computation time per iteration. We first prove that the order of retiming and unfolding is immaterial for scheduling a data-flow graph (DFG). From this nice property, we present a polynomial-time algorithm on the original DFG, before unfolding, to find the minimum-rate static schedule for a given unfolding factor. For the case of a unit-time DFG, efficient checking and retiming algorithms are presented.

关键词： data-flow graphs loop parallelization parallel processing retiming scheduling unfolding

来源：评论

学校读者我要写书评

暂无评论

INCORPORATING INPUT-OUTPUT OPERATIONS INTO DYNAMIC data-flow graphs

引用

PARALLEL COMPUTING 1995年第8期21卷 1285-1311页

作者： EVRIPIDOU, P GAUDIOT, JL UNIV CYPRUS DEPT COMP SCI NICOSIA 134 CYPRUS UNIV SO CALIF DEPT ELECT ENGN SYST LOS ANGELES CA 90089 USA

Driven by the 'side-effect' environment of sequential von Neumann computing, Input/Output operations have evolved as state operations on shared files. In parallel programs, if multiple instances of an I/O-performing process execute concurrently, either the user or the system must synchronize any accesses to shared files. data-flow principles of execution provide an elegant way to ensure at runtime that instructions can be executed asynchronously in a parallel environment. However, while the conventional von Neumann model of interpretation inherited a rigid ordering of instructions, it is the very asynchronous character of the data-flow model of execution which introduces conflicts when 'state' tasks (such as I/O operations) must share common data objects. The scheme presented in this paper, Logical Serialization with Distributed File Pointers (LS-DFP), introduces the two basic I/O operations read and write into the dynamic data-flow graph. However, sequencing I/O operations on the same file based on the availability of data as in 'conventional' data-flow is not possible because the name of the file becomes available simultaneously to ail operations at program initiation. To impose an order, we sequentialize, (logically serialize-LS), the operations according to their lexicographical ordering. Furthermore, several optimizations are introduced that allow the distributed execution of these I/O operations with the use of Distributed File Pointers (DFP). Thus, the LS-DFP scheme can utilize the full level of parallelism of the dynamic data-flow principles of execution.

关键词： data-flow graphs PARALLEL I/O OPERATIONS DISTRIBUTED FILE POINTERS I/O SYNCHRONIZATION PROBLEM INPUT ACCESS GRAPH (IAG)

来源：评论

学校读者我要写书评

暂无评论

GraphCL: A Framework for Execution of data-flow graphs on Multi-Device Platforms 30

GraphCL: A Framework for Execution of Data-Flow Graphs on Mu...

引用

30th Euromicro International Conference on Parallel, Distributed and Network-Based Processing (PDP)

作者： Moren, Konrad Goehringer, Diana Fraunhofer IOSB Dept Object Recognit Ettlingen Germany Tech Univ Dresden Chair Adapt Dynam Syst Dresden Germany

ISBN: (纸本)9781665469586

This article introduces GraphCL, an automated system for seamlessly mapping multi-kernel applications to multiple computing devices. GraphCL, consists of a C ++ API and a runtime that abstracts and simplifies the execution of multi-kernel applications on heterogeneous platforms across multiple devices. The GraphCL approach has three steps. First, the application designer provides a kernel graph. In the second phase, GraphCL computes the execution schedule. After the schedule has been computed, the runtime uses the execution schedule to enqueue in parallel the processing for all system processors. GraphCL takes the kernel dependencies and the processor performance differences into account during the schedule calculation process. By deciding on the schedule, GraphCL transparently manages the order of execution and data transfers for each processor. On two asymmetric workstations, GraphCL achieves an average acceleration of 1.8x compared to the fastest device. GraphCL achieves also for the set of multi-kernel benchmarks an average 24.5% energy reduction compared to the lazy partition heuristic. that uses all the system processors without considering their power usage.

关键词： data-flow graphs GPGPU OpenCI

来源：评论

学校读者我要写书评

暂无评论

An Efficient Error Estimation Technique for Pruning Approximate data-flow graphs in Design Space Exploration 23

An Efficient Error Estimation Technique for Pruning Approxim...

引用

23rd International Symposium on Quality Electronic Design (ISQED)

作者： Vaeztourshizi, Marzieh Pedram, Massoud Univ Southern Calif Dept Elect Comp Engn Los Angeles CA 90007 USA

ISBN: (纸本)9781665494663

In this paper, we present an error estimation and propagation technique which targets high-level design abstraction through considering data-flow graph (DFG) representation of approximate circuits. The proposed technique is utilized for pruning different combinations of exact versus approximate realizations of various operations in the DFG for a design space exploration (DSE) framework The technique relies on the output error estimation of the arithmetic modules of a high-level library by dividing the input range to intervals and then considering different combinations of these intervals (cluster-based estimation of output error). Additionally, the estimation considers the error of the operands. The error for each combination is stored in a look up table (LUT). The efficacy of the proposed method is assessed for two image processing applications. Simulation results show that the framework can efficiently generate the Pareto frontier in the trade-off space of accuracy versus energy efficiency for the two applications.

关键词： Approximate Circuits Error Estimation Pareto Frontier data-flow graphs Look up Tables Error Metrics

来源：评论

学校读者我要写书评

暂无评论

Disproving the perfect-rate property of data-flow graphs unfolded by the least common multiple of the number of loop registers

引用

IEEE TRANSACTIONS ON COMPUTERS 2003年第5期52卷 688-688页

作者： Wolz, F Kolla, R Univ Wurzburg Dept Comp Engn D-97070 Wurzburg Germany

In the paper "Static Rate-Optimal Scheduling of Iterative data-flow Programs via Optimum Unfolding" [1], the authors stated a perfect-rate property on unfolded data-flow graphs (DFGs) This will be disproven ... 详细信息

关键词： data-flow graphs data-flow programs perfect-rate

来源：评论

学校读者我要写书评

暂无评论

Optimal Functional-Unit Assignment for Heterogeneous Systems Under Timing Constraint

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2017年第9期28卷 2567-2580页

作者： Jiang, Weiwen Sha, Edwin Hsing-Mean Chen, Xianzhang Yang, Lei Zhou, Lei Zhuge, Qingfeng Chongqing Univ Coll Comp Sci Chongqing 400044 Peoples R China

In high-level synthesis for real-time systems, it typically employs heterogeneous functional-unit types to achieve high-performance and low-cost designs. In the design phase, it is critical to determine which functional-unit type to be mapped for each operation in a given application such that the total cost is minimized while the deadline can be met. For a path or tree structured application, existing approaches can obtain the minimum-cost assignment, called "optimal assignment", under which the resultant system satisfies a given timing constraint. However, it is still an open question whether there exist efficient algorithms to obtain the optimal assignment for the directed acyclic graph (DAG), or more generally, the data-flow graph with cycles (cyclic DFG). For DAGs, by analyzing the property of the problem, this paper designs an efficient algorithm to obtain the optimal assignments. For cyclic DFGs, we approach this problem with the combination of retiming technique to thoroughly explore the design space. We formulate a Mixed Integer Linear Programming (MILP) model to give the optimal solution. But because of the high degree of its time complexity, we devise a practical algorithm to obtain near-optimal solutions within a minute. Experimental results show the effectiveness of our algorithms. Specifically, compared with existing techniques, we can achieve 25.70 and 30.23 percent reductions in total cost on DAGs and cyclic DFGs, respectively.

关键词： Real-time heterogeneous system data-flow graphs functional-unit assignment retiming optimal algorithms

来源：评论

学校读者我要写书评

暂无评论

An Integrated Approach to Locality-Conscious Processor Allocation and Scheduling of Mixed-Parallel Applications

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2009年第8期20卷 1158-1172页

作者： Vydyanathan, Naga Krishnamoorthy, Sriram Sabin, Gerald M. Catalyurek, Umit V. Kurc, Tahsin Sadayappan, Ponnuswamy Saltz, Joel H. Siemens Corp Technol Bangalore 560100 Karnataka India Pacific NW Natl Lab Richland WA 99352 USA RNET Technol Inc Dayton OH 45459 USA Ohio State Univ Dept Biomed Informat Columbus OH 43210 USA Ohio State Univ Dept Comp Sci & Engn Columbus OH 43210 USA

Complex parallel applications can often be modeled as directed acyclic graphs of coarse-grained application tasks with dependences. These applications exhibit both task and data parallelism, and combining these two ( also called mixed parallelism) has been shown to be an effective model for their execution. In this paper, we present an algorithm to compute the appropriate mix of task and data parallelism required to minimize the parallel completion time (makespan) of these applications. In other words, our algorithm determines the set of tasks that should be run concurrently and the number of processors to be allocated to each task. The processor allocation and scheduling decisions are made in an integrated manner and are based on several factors such as the structure of the task graph, the runtime estimates and scalability characteristics of the tasks, and the intertask data communication volumes. A locality-conscious scheduling strategy is used to improve intertask data reuse. Evaluation through simulations and actual executions of task graphs derived from real applications and synthetic graphs shows that our algorithm consistently generates schedules with a lower makespan as compared to Critical Path Reduction (CPR) and Critical Path and Allocation (CPA), two previously proposed scheduling algorithms. Our algorithm also produces schedules that have a lower makespan than pure task- and data-parallel schedules. For task graphs with known optimal schedules or lower bounds on the makespan, our algorithm generates schedules that are closer to the optima than other scheduling approaches.

关键词： Processor allocation scheduling mixed parallelism data-flow graphs locality-conscious scheduling

来源：评论

学校读者我要写书评

暂无评论

A SCALABLE SCHEDULING SCHEME FOR FUNCTIONAL PARALLELISM ON DISTRIBUTED-MEMORY MULTIPROCESSOR SYSTEMS

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 1995年第4期6卷 388-399页

作者： PANDE, S AGRAWAL, DP MAUNEY, J N CAROLINA STATE UNIV DEPT ELECT & COMP ENGNRALEIGHNC 27695

We attempt a new variant of the scheduling problem by investigating the scalability of the schedule length with the required number of processors, by performing scheduling partially at compile time and partially at run time. Assuming infinite number of processors, the compile time schedule is found using anew concept of the threshold of a task that quantifies a trade-off between the schedule-length and the degree of parallelism, The schedule is found to minimize either the schedule length dr the number of required processors and it satisfies: A feasibility, condition which guarantees that the schedule delay of a task from its earliest start time is below the threshold, and An optimality condition which uses a merit function to decide the best task-processor match for a set of tasks competing for a given processor. At run time, the tasks re merged producing a schedule for a smaller number of available processors,This allows the program to be scaled down to the processors actually available at run time, Usefulness of this scheduling heuristic has been demonstrated by. incorporating the scheduler in the compiler backend for targeting Sisal (Streams and Iterations in a Single Assignment Language) on iPSC/860.

关键词： COMPILE TIME SCHEDULING data-flow graphs DISTRIBUTED MEMORY MULTIPROCESSORS FUNCTIONAL PARALLELISM RUNTIME SCHEDULING SCALING SCHEDULE LENGTH

来源：评论

学校读者我要写书评

暂无评论

HOW TO PROGRAM AND CONFIGURE A HETEROGENEOUS MULTIPROCESSOR

引用

MACHINE VISION AND APPLICATIONS 1993年第1期7卷 30-36页

作者： ZELTNER, M SCHNEUWLY, B GUGGENBUHL, W Electronics Laboratory Swiss Federal Institute of Technology Zürich Switzerland

This paper describes a software environment that allows the programming and configuration of a heterogeneous multiprocessor architecture consisting of specialized hardware and a general purpose trasputer net. Run-time-behavior estimation is done at a compile time by using directed dataflow graphs to represent the program and a database containing all the relevant information about functions. The system offers the implementations of functions running on different hardware platforms, static configuration and scheduling, and integrated performance measurement. We show how programmers can handle such a system without any deeper knowledge of the underlying specialized hardware.

关键词： HETEROGENEOUS MULTIPROCESSOR COMPILE-TIME ANALYSIS STATIC CONFIGURATION SCHEDULING data-flow graphs

来源：评论

学校读者我要写书评

暂无评论

A MODEL FOR THE PARALLEL EXECUTION OF SUBSET-EQUATIONAL LANGUAGES

引用

FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF GRID COMPUTING AND ESCIENCE 1995年第3期11卷 295-320页

作者： OMONDI, AR PLAISTED, DA UNIV N CAROLINA DEPT COMP SCI CHAPEL HILL NC 27599 USA

This paper describes a model for the parallel execution of subset-equational languages, a class of functional languages that allow constrained nondeterminism. The fundamentals of subset-equational languages are presented, followed by the formulation of a kernel language that is used as the basis of the model. The languages are based on nondeterministic term-rewriting systems;the model uses dataflow execution graphs and is suitable for implementation on both conventional and unconventional machines.

关键词： PARALLEL PROCESSING SUBSET-EQUATION LANGUAGES NONDETERMINISM data-flow graphs TERM-REWRITING FUNCTIONAL LANGUAGES

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：