APGAN and RPMC: Complementary Heuristics for Translating DSP Block Diagrams into Efficient Software Implementations
APGAN and RPMC: Complementary Heuristics for Translating DSP Block Diagrams into Efficient Software Implementations
复制标题
APGAN 和 RPMC：将 DSP 框图转换为高效软件实现的互补启发法
DOI：
--
复制
发表时间：
1997
影响因子：
1.4
通讯作者：
Edward A. Lee
中科院分区：
文献类型：
--
作者：
S. Bhattacharyya;P. Murthy;Edward A. Lee
数据流已被证明是图形化DSP设计环境的一个有吸引力的计算模型，它支持将分层信号流图自动转换为可编程处理器上的实现。同步数据流（SDF）模型特别适合于基于数据流的图形化编程，因为它的受限语义提供了强大的形式属性和重要的编译时可预测性，同时捕获了大量重要信号处理应用程序的行为。当为嵌入式信号处理应用程序合成软件时，由于内存有限而产生关键约束。在本文中，我们提出了一种解决在将SDF程序转换为软件实现时共同优化代码和数据大小问题的解决方案。我们考虑两种方法。第一个是自底向上技术对无环图的自定义，称为相邻节点的成对分组（PGAN），这是前面为一般SDF图提出的。我们表明，我们对无环图的定制显着降低了一般PGAN算法的复杂性，并且我们提出了对我们改进的PGAN技术的正式研究，该技术严格地建立了其对某类应用的最优性。我们考虑的第二种方法是基于广义最小切割操作的自顶向下技术，该技术最近在b[14]中被引入。我们提出了对改进的PGAN技术和自上而下方法的性能以及它们之间的权衡进行广泛实验研究的结果。根据这些结果，我们得出结论，这两种技术相互补充，因此，它们都应该被纳入基于sdf的软件实现环境中，在这种环境中，最小化内存需求是很重要的。我们已经在加州大学伯克利分校的托勒密软件环境[5]中实现了这些算法。
Dataflow has proven to be an attractive computational model for graphical DSP design environments that support the automatic conversion of hierarchical signal flow diagrams into implementations on programmable processors. The synchronous dataflow (SDF) model is particularly well-suited to dataflow-based graphical programming because its restricted semantics offer strong formal properties and significant compile-time predictability, while capturing the behavior of a large class of important signal processing applications. When synthesizing software for embedded signal processing applications, critical constraints arise due to the limited amounts of memory. In this paper, we propose a solution to the problem of jointly optimizing the code and data size when converting SDF programs into software implementations.We consider two approaches. The first is a customization to acyclic graphs of a bottom-up technique, called pairwise grouping of adjacent nodes (PGAN), that was proposed earlier for general SDF graphs. We show that our customization to acyclic graphs significantly reduces the complexity of the general PGAN algorithm, and we present a formal study of our modified PGAN technique that rigorously establishes its optimality for a certain class of applications. The second approach that we consider is a top-down technique, based on a generalized minimum-cut operation, that was introduced recently in [14]. We present the results of an extensive experimental investigation on the performance of our modified PGAN technique and the top-down approach and on the trade-offs between them. Based on these results, we conclude that these two techniques complement each other, and thus, they should both be incorporated into SDF-based software implementation environments in which the minimization of memory requirements is important. We have implemented these algorithms in the Ptolemy software environment [5] at UC Berkeley.