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

Re-scheduling invocations of services for RPC grids

COMPUTER LANGUAGES SYSTEMS & STRUCTURES 2007年第3-4期33卷 168-178页

作者： Gautier, Thierry Hamidi, Hamid-Reza Project APACHE Lab ID IMAG F-38330 Montbonnot St Martin France

RPC-based grid infrastructures emphasize on the composition of services on a large number of computing resources. The key issue to reach high performance is to enable exploitation of parallelism on services invocations and communications. Moreover, this process should be transparent to reuse legacy codes. In this paper we present HOMA, an IDL compiler and a run-time support for automatic detection of the parallelism of invocations and their data dependencies on a set of CORBA objects. On homogeneous architecture, HOMA is accompanied by a predictable cost model. In the case of an application with a small critical path, among p processors the speed up of HoMA versus CORBA is asymptotically 0(p). The illustrations on a case study in computational chemistry validate our cost model. (c) 2006 Published by Elsevier Ltd.

关键词： method invocations data flow graph predictive cost model CORBA

来源：评论

学校读者我要写书评

暂无评论

A scheduling algorithm for optimization and early planning in high-level synthesis

引用

ACM TRANSACTIONS ON DESIGN AUTOMATION OF ELECTRONIC SYSTEMS 2005年第1期10卷 33-57页

作者： Memik, SO Kastner, R Bozorgzadeh, E Sarrafzadeh, M Northwestern Univ Dept Elect & Comp Engn Evanston IL 60208 USA Univ Calif Santa Barbara Dept Elect & Comp Engn Santa Barbara CA 93106 USA Univ Calif Irvine Dept Comp Sci Irvine CA 92697 USA Univ Calif Los Angeles Dept Comp Sci Los Angeles CA 90095 USA

Complexities of applications implemented on embedded and programmable systems grow with the advances in capacities and capabilities of these systems. Mapping applications onto them manually is becoming a very tedious task. This draws attention to using high-level synthesis within design flows. Meanwhile, it is essential to provide a flexible formulation of optimization objectives as well as to perform efficient planning for various design objectives early on in the design flow. In this work, we address these issues in the context of data flow graph (DFG) scheduling, which is an essential element within the high-level synthesis flow. We present an algorithm that schedules a chain of operations with data dependencies among consecutive operations at a single step. This local problem is repeated to generate the schedule for the whole DFG. The local problem is formulated as a maximum weight noncrossing bipartite matching. We use a technique from the computational geometry domain to solve the matching problem. This technique provides a theoretical guarantee on the solution quality for scheduling a single chain of operations. Although still being local, this provides a relatively wider perspective on the global scheduling objectives. In our experiments we compared the latencies obtained using our algorithm with the optimal latencies given by the exact solution to the integer linear programming (ILP) formulation of the problem. In 9 out of 14 DFGs tested, our algorithm found the optimal solution, while generating latencies comparable to the optimal solution in the remaining five benchmarks. The formulation of the objective function in our algorithm provides flexibility to incorporate different optimization goals. We present examples of how to exploit the versatility of our algorithm with specific examples of objective functions and experimental results on the ability of our algorithm to capture these objectives efficiently in the final schedules.

关键词： design algorithms scheduling high-level synthesis data flow graph bipartite matching

来源：评论

学校读者我要写书评

暂无评论

Decomposition of extended finite state machine for low power design 03

Decomposition of extended finite state machine for low power...

引用

IEL Citation

作者： MingHung Lee TingTing Hwang Shi-Yu Huang National Tsing Hua University

ISBN: (纸本)0769518702

Power reduction can be achieved by turning off portions of circuits that are idle. Unlike previous work, which focused only on either controller or data-path, we propose a decomposition technique that takes both controller and data-path into consideration where, in the former, the state probability of an FSM provides the execution frequency of operations in that state. And, in the latter, operations performed in states provide the information of resource requirements which can be used to determine the resource sharing among states. The goal is to synthesize circuits such that the submachine with small area (data-path and controller) will be turned on most of the time (high state probability) and all other parts are turned off. Our experimental results show that on the average, 101 % area reduction and 24 % power reduction can be achieved as compared with designs without decomposition.

关键词： finite state machines logic design low-power electronics data flow graphs data flow graph EFSM decomposition extended finite state machine low power design power reduction idle circuit turn off FSM controller FSM data-path FSM state probability resource sharing area reduction

来源：评论

学校读者我要写书评

暂无评论

Novel neighborhood search for multiprocessor scheduling with pipelining

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2002年第1期62卷 85-110页

作者： Leung, KK Yung, NHC Cheung, PYS Univ Hong Kong Dept Elect & Elect Engn Hong Kong Hong Kong Peoples R China

This paper presents a neighborhood search algorithm for heterogeneous multiprocessor scheduling in which loop pipelining is used to exploit parallelism between iterations. The method adopts a realistic model for interprocessor communication where resource contention is taken into consideration. The schedule representation scheme is flexible so that communication scheduling can be performed in a generic manner. Base on a general time formulation of the schedule performance, the algorithm improves an initial schedule in an efficient way by successive modification to the task processor mapping and task ordering. Simulation results show that significant improvement over existing methods can be obtained. A parallel software video encoder was implemented based on the scheduling result and real time performance was achieved with pipelining of frame encoding. (C) 2001 Elsevier Science.

关键词： neighborhood search multiprocessor scheduling interprocessor communication data flow graph pipelining

来源：评论

学校读者我要写书评

暂无评论

Semiconcurrent error detection in data paths

引用

IEEE TRANSACTIONS ON COMPUTERS 2001年第5期50卷 449-465页

作者： Antola, A Ferrandi, F Piuri, V Sami, M Politecn Milan Dept Elect & Informat I-20133 Milan Italy Univ Milan Dept Informat Technol I-26013 Crema CR Italy

A high-level synthesis strategy is proposed for design of semiconcurrently self-checking devices. Attention is mainly focused on data path design. After identifying the reference architecture against which cost and performance are evaluated. a simultaneous scheduling-and-allocation strategy is presented for linear-code data flow graphs, allowing resource sharing between nominal and checking data paths. The proposed strategy is actually independent from a specific scheduling-and-allocation algorithm since it is essentially concerned with the introduction of the fault tolerance issue at high-abstraction level in any design environment. Conventional duplication with comparison, even if considered in a high-level synthesis strategy, leads to high circuit complexity increase. The proposed approach provides that the required checking periodicity is satisfied while minimizing additional functional units by means of maximum reuse of the resources available for the nominal computation as long as error detection ability is preserved. The strategy is then extended to deal with branches and loops in the data path. Risk of error aliasing due to resource sharing is analyzed.

关键词： semiconcurrent error detection self-checking circuits checking periodicity fault tolerance high-level synthesis data flow graph resource minimization

来源：评论

学校读者我要写书评

暂无评论

Adaptive parallel video coding algorithm

Adaptive parallel video coding algorithm

引用

Conference on Visual Communications and Image Processing 2001

作者： Leung, KK Yung, NHC Cheung, PYS Univ Hong Kong Dept Elect & Elect Engn Hong Kong Hong Kong Peoples R China

ISBN: (纸本)0819439886

Parallel encoding of video inevitably gives varying frame rate performance due to dynamically changing video content and motion field since the encoding process of each macro-block, especially motion estimation, is data dependent. A multiprocessor schedule optimized for a particular frame with certain macro-block encoding time may not be optimized towards another frame with different encoding time, which causes performance degradation to the parallelization. To tackle this problem, we propose a method based on a batch of near-optimal schedules generated at compile-time and a run-time mechanism to select the schedule giving the shortest predicted critical path length. This method has the advantage of being near-optimal using compile-time schedules while involving only run-time selection rather than re-scheduling. Implementation on the IBM SP2 multiprocessor system using 24 processors gives an average speedup of about 13.5 (frame rate of 38.5 frames per second) for a CIF sequence consisting of segments of 6 different scenes. This is equivalent to an average improvement of about 16.9% over the single schedule scheme with schedule adapted to each of the scenes. Using an open test sequence consisting of 8 video segments, the average improvement achieved is 13.2%, i.e. an average speedup of 13.3 (35.6 frames per second).

关键词： video coding multiprocessor scheduling inter-processor communication data flow graph pipelining H.261

来源：评论

学校读者我要写书评

暂无评论

Buffer assignment algorithms on data driven ASICs

引用

IEEE TRANSACTIONS ON COMPUTERS 2000年第1期49卷 16-32页

作者： Chatterjee, M Banerjee, S Pradhan, DK Integrated Device Technol Inc MPR Syst Level Prod Santa Clara CA 95054 USA Bell Labs Lucent Technol Allentown PA 18103 USA Digital Res Inc College Stn TX 77845 USA

data driven architectures have significant potential in the design of high performance ASICs. By exploiting the inherent parallelism in the application, these architectures can maximize pipelining. The key consideration involved with the design of a data driven ASIC is ensuring that throughput is maximized while a relatively low area is maintained. Optimal throughput can be realized by ensuring that all operands arrive simultaneously at their corresponding operator node, if this condition is achieved, the underlying data flow graph is said to be balanced. If the initial data flow graph is unbalanced, buffers must be inserted td prevent the clogging of the pipeline along the shorter paths. A novel algorithm for the assignment of buffers in a data flow graph is proposed. The method can also be applied to achieve wave-pipelining in digital systems under certain restrictions. The algorithm uses a new application of the retiming technique;the number of buffers here is shown to be equal to the minimum number of buffers achieved by integer programming techniques. We also discuss an extension of this algorithm which can further reduce the number of buffers by altering the DFO without affecting functionality or performance. The time complexities of the proposed algorithms are O(V x E) and O(V-2 x logV), respectively, a considerable improvement over the existing strategies. Also proposed is a novel buffer distribution algorithm that exploits a unique feature of data driven operation. This procedure maximizes throughput by inserting substantially fewer buffers than other techniques. Experimental results show that the proposed algorithms outperform the existing methods.

关键词： application specific integrated circuits data driven architecture data flow graph throughput buffers wave-pipelining

来源：评论

学校读者我要写书评

暂无评论

Buffer memory requirements in DSP applications

引用

COMPUTER SYSTEMS SCIENCE AND ENGINEERING 1999年第3期14卷 155-165页

作者： Adé, M Lauwereins, R Peperstraete, JA Katholieke Univ Leuven ESAT Dept B-3001 Heverlee Belgium

In this paper, we study consistent synchronous multi-rate data flow graphs to determine the minimal required buffer sizes that still guarantee the construction of a deadlock-free static schedule. A graph is split up in chains and clusters that can be studied independently. We present the results for chains, as well as for the most frequent clusters. The results will be used in the rapid prototyping environment GRAPE-II in case the emulation hardware contains FPGAs, or when memory is critical.

关键词： Digital Signal Processing data flow graph buffer memory minimisation deadlock-free static schedule

来源：评论

学校读者我要写书评

暂无评论

Scheduling and variable binding for improved testability in high level synthesis

引用

COMPUTERS & ELECTRICAL ENGINEERING 1998年第6期24卷 441-461页

作者： Ismaeel, AA Mathew, R Bhatnagar, R Kuwait Univ Coll Engn & Petr Dept Elect & Comp Engn Kuwait 13060 Kuwait

In this paper, we present a scheduling and a variable binding technique for improved testability in high level synthesis. The scheduling technique called cost based scheduling system (CBSS), is time constrained which minimizes the number of resources (operations) and the number of registers based on a cost function. The CBSS improves the life time of primary input and primary output variables, reduces the life times of intermediate variables and hence improves the controllability and observability. The testability of the register transfer level (RTL) structure generated by this schedule is therefore improved. CBSS considers all the variables and operations jointly for scheduling. CBSS supports various scheduling modes such as multicycled and chained operations, and pipelining. The complexity of our scheduling algorithm is O(c.n(2)) where c is the number of control steps and II is the number of operations to be scheduled. To generate a highly testable RTL structure, the CBSS is followed by a variable binding technique to bind the variables into registers. An integer linear programming (ILP) approach is proposed with an objective function that minimizes the number of registers and a set of constraints that improves the testability of the RTL structure. Various case studies are presented and the results on different benchmark examples show the potential of our approach. (C) 1998 Elsevier Science Ltd. All rights reserved.

关键词： data flow graph scheduling binding design for testability

来源：评论

学校读者我要写书评

暂无评论

Scheduling with multiple voltages

引用

INTEGRATION-THE VLSI JOURNAL 1997年第1期23卷 37-59页

作者： Raje, S Sarrafzadeh, M Northwestern Univ Dept Elect Engn & Comp Sci Evanston IL 60208 USA

This paper presents a low power design technique at the behavioral synthesis stage. A scheduling technique for low power is studied and a theoretical foundation is established. The equation for dynamic power, P-dyn=V(dd)(2)C(load)f(switch), is used as a basis. The voltage applied to the functional units is varied, slowing down the functional unit throughput and reducing the power while meeting the throughput constraint for the entire system. The input to our problem is an unscheduled data flow graph with a timing constraint. The goal is to establish a voltage value at which each of the operations of the data flow graph would be performed, thereby fixing the latency for the operation such that the total timing constraint for the system is met. We give an algorithm to minimize the system's power;the algorithm finds an optimal schedule. The timing constraint for our system could be any value greater than or equal to the critical path. The experimental results for some high-level synthesis benchmarks show considerable reduction in the power consumption. Using 5 and 3 V supply voltages we achieve a maximum reduction of approximately 40% given tight timing constraints. Similarly, we obtain a 46% reduction using 5, 3 and 2.4 V supply voltages. For larger timing constraints, the maximum reduction is about 64% using 5 and 3 V supply voltages and a maximum reduction of about 74% using 5, 3 and 2.4 V supply voltages.

关键词： data flow graph scheduling behavioral synthesis low-power design multiple voltages

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：