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

Evaluation of the Exact Throughput of a synchronous dataflow graph

JOURNAL OF SIGNAL PROCESSING SYSTEMS FOR SIGNAL IMAGE AND VIDEO TECHNOLOGY 2021年第9期93卷 1007-1026页

作者： Bodin, Bruno Kordon, Alix Munier Natl Univ Singapore Yale NUS Coll Sch Comp Singapore Singapore Sorbonne Univ CNRS LIP6 F-75005 Paris France

synchronous dataflow graph (SDFG in short) is a formalism frequently considered in electronic design and software compilers to model communications between components with different rates. The development of efficient algorithms to evaluate the maximum throughput of SDFGs is a challenging question. This paper presents a mathematical framework to perform schedulability analysis and to compute the maximum throughput of SDFGs. This work focuses on strictly K-Periodic schedules for which a fixed set of execution times coupled with a period are associated with each task and define a schedule of every task executions. This class of schedules can always reach maximal throughput;we present an algorithm that computes the exact maximum throughput by iteratively generating K-periodic schedules until we reach optimality. The complexity of this iterative algorithm is studied by using the well-established benchmarking suite SDF3, and compared against the most common throughput analysis techniques. We show several orders of magnitude improvement over state-of-the-art both in terms of computation time, and size of the final schedules.

关键词： synchronous dataflow graph maximum throughput K-periodic scheduling

来源：评论

学校读者我要写书评

暂无评论

Computing latency of a real-time system modeled by synchronous dataflow graph 16

Computing latency of a real-time system modeled by Synchrono...

引用

24th International Conference on Real-Time Networks and Systems (RTNS)

作者： Khatib, Jad Munier-Kordon, Alix Klikpo, Enagnon Cedric Trabelsi-Colibet, Kods CEA LIST F-91191 Gif Sur Yvette France Sorbonne Univ F-75252 Paris France SystemX IRT F-91120 Palaiseau France

ISBN: (纸本)9781450347877

Mixed applications that gather real-time tasks and best effort jobs require a research effort in order to be effectively modeled and executed. Therefore, in this study we define a general and intuitive communication model between multi-periodic real-time tasks. We first demonstrate that the communications between real-time tasks can be directly expressed as a "synchronous Data-flow graph". This modeling allows precise definition of the system latency. Accordingly, we develop an exact evaluation method to calculate the worst case latency of a system from a given input to a connected outcome. Then, we frame this value using two algorithms that compute its upper and lower bounds. Finally, we show that these bounds can be computed using a polynomial amount of computation time, while the time required to compute the exact value increases linearly according to the average repetition factor. Furthermore, the gap between the exact result and its upper (resp. lower) bound is evaluated between 10 and 15 % (resp. 20 and 30%).

关键词： Real-time system synchronous dataflow graph latency

来源：评论

学校读者我要写书评

暂无评论

Evaluation of synchronous dataflow graph Mappings onto Distributed Memory Architectures. 19

Evaluation of Synchronous Dataflow Graph Mappings onto Distr...

引用

19th Euromicro Conference on Digital System Design (DSD)

作者： Lesparre, Youen Munier-Kordon, Alix Delosme, Jean-Marc Univ Paris 06 Sorbonne Univ CNRS LIP6 Paris France Univ Evry Val dEssonne IBISC F-91025 Evry France

ISBN: (纸本)9781509028160

The search of a mapping of a synchronous Data Flow graph (SDFG) on a distributed architecture that achieves a given throughput while satisfying memory constraints is a difficult challenge. Solving this problem calls for evaluating throughput and buffer capacities associated to a mapping. Since the available mapping evaluation methods are not polynomial with respect to the SDFG description, mapping techniques using them are not scalable. This paper develops a polynomial method for the evaluation of any given SDFG mapping on a distributed architecture. The method is based on a simple transformation of the SDFG to model communications through a Network on Chip. The key result is that the size of the memory required in order to guarantee the liveness or a given throughput of an application may be evaluated in polynomial time. Experimentally, computing the memory size guaranteeing liveness of a mapping of a 670-node H264 graph on a 4-cluster architecture takes 70 ms on an Intel Core i5-660 processor and grows linearly with graph size.

关键词： Distributed Memory Architecture Liveness Mapping synchronous dataflow graph Throughput Constraint

来源：评论

学校读者我要写书评

暂无评论

Worst-Case Response Time Analysis of a synchronous dataflow graph in a Multiprocessor System with Real-Time Tasks

引用

ACM TRANSACTIONS ON DESIGN AUTOMATION OF ELECTRONIC SYSTEMS 2017年第2期22卷 36-36页

作者： Choi, Junchul Ha, Soonhoi Seoul Natl Univ Dept Comp Sci & Engn 1 Gwanak Ro Seoul 151742 South Korea

In this article, we propose a novel technique that estimates a tight upper bound of the worst-case response time (WCRT) of a synchronous dataflow (SDF) graph when the SDF graph shares processors with other real-time tasks. When an SDF graph is executed at runtime under a self-timed or static assignment scheduling policy on a multi-processor system, static scheduling of the SDF graph does not guarantee the satisfaction of latency constraints since changes to the schedule may result in timing anomalies. To estimate the WCRT of an SDF graph with a given mapping and scheduling result, we first construct a task instance dependency graph that depicts the dependency between node executions in a static schedule. The proposed technique combines two techniques in a novel way: schedule time bound analysis and response time analysis. The former is used to consider the interference between task instances in the same SDF graph, and the latter is used to consider the interference from other real-time tasks. Through extensive experiments with synthetic examples and benchmarks, we verify the superior performance of the proposed technique compared to other existent techniques.

关键词： synchronous dataflow graph worst-case response time performance analysis response time analysis partitioned scheduling real-time system multiprocessor

来源：评论

学校读者我要写书评

暂无评论

Mapping of synchronous dataflow graphs on MPSoCs based on parallelism enhancement

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2017年 101卷 79-91页

作者： Tang, Qi Basten, Twan Geilen, Marc Stuijk, Sander Wei, Ji-Bo Natl Univ Def Technol Dept Elect Sci & Engn Changsha Hunan Peoples R China Eindhoven Univ Technol Dept Elect Engn Eindhoven Netherlands TNO Embedded Syst Innovat Eindhoven Netherlands

Multi-processor systems-on-chips are widely adopted in implementing modern streaming applications to satisfy the ever increasing computation requirements. To take advantage of this kind of platform, it is necessary to map tasks of the application properly to different processors, so as to fully exploit the inherent task-level parallelism and satisfy the stringent timing requirements. We propose the Parallelism graph to capture the task-level parallelism of the application and transform the mapping problem to a graph partitioning problem. The graph partitioning problem is formulated as an Integer Linear Programming problem, which is solved optimally using the ILP solver. To reduce the complexity, a two-step local search algorithm, i.e., the greedy partition and refinement algorithm, is proposed. Since one-shot heuristics cannot guarantee the solution quality, evolutionary algorithms are widely used to search the solution space such that better results can be found. We also integrate the idea of parallelism enhancement into the genetic algorithm and propose a hybrid genetic algorithm to improve the performance. Sets of synthesized synchronous Data Flow graphs and some practical applications are used to evaluate the performance of the proposed algorithms. Experiment results demonstrate that the proposed algorithms outperform available algorithms. (C) 2016 Elsevier Inc. All rights reserved.

关键词： synchronous dataflow graph Multiprocessor Mapping graph partition Genetic algorithm

来源：评论

学校读者我要写书评

暂无评论

Memory optimal single appearance schedule with dynamic loop count for synchronous dataflow graphs 06

Memory optimal single appearance schedule with dynamic loop ...

引用

11th Asia and South Pacific Design Automation Conference

作者： Oh, Hyunok Dutt, Nikil Ha, Soonhoi Univ Calif Irvine Ctr Embedded Comp Syst Irvine CA 92697 USA Seoul Natl Univ Sch EECS Seoul South Korea

ISBN: (纸本)0780394518

In this paper, we propose a new single appearance schedule for synchronous dataflow programs to minimize data memory and code memory size simultaneously. While a single appearance schedule promises only one appearance of each node definition in the generated code, it requires significant amount of data memory overhead compared with a buffer optimal schedule allowing multiple appearance. The key idea of the proposed technique is to make a dynamic decision of loop count to make a schedule quasi-static. The proposed quasi-static schedule produces a single appearance schedule code with minimum data memory requirement. We prove that every buffer optimal schedule can be transformed to our single appearance schedule which requires optimal buffer size for arbitrary synchronous dataflow graphs. The only penalty for the proposed technique is slight performance overhead of computing loop counts dynamically. In order to minimize the overhead we propose optimization techniques. Experimental results show that the proposed algorithm reduces 20% total memory with less than 1% performance overhead compared with the previous single appearance schedule algorithms.

关键词： data flow graphs processor scheduling storage management code memory dynamic decision dynamic loop count loop counts memory optimal single appearance schedule minimum data memory schedule code schedule quasi-static synchronous dataflow graph

来源：评论

学校读者我要写书评

暂无评论

An energy aware buffer mapping technique on hybrid STT-MRAM memories with multiple retention time for stream applications

引用

DESIGN AUTOMATION FOR EMBEDDED SYSTEMS 2013年第3-4期17卷 693-710页

作者： Choi, Kwangil Oh, Hyunok Hanyang Univ Dept Informat Syst Seoul 133791 South Korea

STT-MRAM has been recently researched to replace DRAM in order to reduce the cell size and save the leakage power consumption. Although the read operation in STT-MRAM is acceptable in terms of performance and energy consumption, the write operation discourages the adoption of the STT-MRAM as main memory. A promising approach to overcome the poor write operation is to reduce the planar cell size which decreases the retention time, the write latency and the write energy consumption since the change of the cell size requires no additional manufacturing process. However, since refresh is required in the reduced retention time memory just like DRAM, the leakage energy consumption may increase compared with a traditional STT-MRAM with long retention time. This paper solves the buffer mapping problem onto a system with multiple retention time memories for a stream application to minimize the energy consumption. Experimental results show that a system with two or three different retention time STT-MRAMs reduces 45-75 % of write energy consumption compared with a single long retention time STT-MRAM.

关键词： STT-MRAM Retention time synchronous dataflow graph Energy minimization Buffer mapping

来源：评论

学校读者我要写书评

暂无评论

A Lifetime Aware Buffer Assignment Method for Streaming Applications on DRAM/PRAM Hybrid Memory

引用

ACM TRANSACTIONS ON EMBEDDED COMPUTING SYSTEMS 2013年第1S期12卷 1–17页

作者： Lee, Daeyoung Oh, Hyunok Hanyang Univ Dept Informat Syst Seoul South Korea

This article proposes a lifetime aware buffer assignment method for streaming applications like multimedia specified in a synchronous dataflow (SDF) graph on a DRAM/PRAM hybrid memory in which the endurance of PRAM is limited. We determine whether buffers are assigned to DRAM or PRAM to minimize the writing frequency of PRAM. To solve the problems, we formulate them using Answer Set Programming. Experimental results show that the proposed approach increases the PRAM lifetime by 63% compared with no optimization, and shows the tradeoff between PRAM and DRAM size to guarantee a lifetime constraint.

关键词： Algorithms Reliability Endurance synchronous dataflow graph schedule phase change RAM

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：