用于NoC映射的EDA工具设计

摘要:片上网络(NoC)作为解决片上系统(SoC)复杂通信问题的新的范例,受到了工业界和学术界的广泛重视。为了保证实时任务在片上网络上的高效运行,从任务到网络拓扑的映射问题成为NoC研究中的关键问题之一。为了得到各种条件下的不同映射结果和性能曲线,本文设计了一种通用的NoC映射EDA工具。该工具基于Matlab的GUI设计方法,具有界面友好、可重配置性、运行速度快、自动导出并存储仿真结果等特点。

关键词:NoC映射;可重配置;EDA工具;GUI

A Novel EDA Tool Designed for NoC Mapping

CHEN Geng-sheng, CHEN Yi-ou, HU Jian-hao

(National Key Laboratory of Science and Technology on Communications

the University of Electronic Science and Technology of China, Chengdu, 610054, China)

Abstract: As a new effective method for solving complex problems of System-on-Chip(SoC), Network-on-Chip (NoC)becomes more and more popular in both industrial and academia. Mapping is one of the key problems in the research of NoC, which is a process about assigning application tasks to a given special NoC platform. In this paper, we designed a general tool for NoC mapping processes to obtain the mapping results and performance curves. This tool is created by GUI method with Matlab tools and has several advantages, including friendly-interface, reconfigurable, fast-runtime, exporting and saving emulation-information automatically and so on.

Key words: NoC mapping;reconfigurable;EDA tools;GUI

1引言

片上系统(SoC,System-on-Chip)自上个世纪90年代被提出之后,逐渐成为下一代集成电路主流技术。在2001年左右,一些研究机构借鉴和吸收了通信网络中的一些思想,提出了以通信网为核心的复杂SoC的知识产权(IP,Intellectual-Property)核集成方法,即片上网络(NoC,Network-on-Chip),以解决复杂SoC面临的各种问题[1]。NoC基础研究涉及从物理层到应用层、从理论到设计方法和工具等诸多方面的问题。本文将重点放在了NoC映射问题的阐述以及能求解映射结果和性能曲线的EDA工具设计,并给出了相关仿真实例。实验结果表明,通过设置不同应用任务、网络拓扑、映射算法、约束、优化目标等初始化条件,该工具能迅速完成映射结果求解和性能曲线的绘制,并具有操作便捷、界面友好、可重配置、仿真关键信息存储等诸多优点。

本文结构如下:在第2节中给出NoC映射问题的一般概述和映射过程中需要考虑的因素;在第3节中详细描述该工具的软件层次结构及其具体特性;第4节将给出使用该工具所得到的一些实验数据和曲线图;最后,第5节作全文总结和展望。

2NoC映射问题

传统的NoC映射问题指将各IP核按照一定的优化规则分配到NoC平台上,实现特定应用,并且使目标成本最小化。这里,每一个IP核可以理解为多个独立不可分解任务的集合。从IP核到NoC平台的映射过程为同一规模映射,即IP核个数不超过NoC路由节点的个数,属于经典的二次分配问题。在本文中,我们提出了一种不同于传统映射过程的映射模型,该模型具有建模简单等特点。

2.1 映射模型

如图1,映射模型由两部分组成:数据流图(DFG,Data-Flow-Graph)和NoC平台(NoC-Platform)。

数据流图可以表征任何一个数字信号实时处理系统。其中,数据节点U代表应用中的基本运算单元或基本功能单元或者一个子任务,而连接数据节点的有向边则表示该数据节点对之间存在单向的数据交互。NoC平台则是片上网络结构的抽象表现形式,网络平台的基本单元Tile集合了具有一定处理能力的处理器、路由节点、缓存等器件。Tile之间的通信需要通过内部路由节点的转发和寻址,而每个Tile内部的器件之间能实现本地资源的共享。这样,这种新的NoC映射模型可以描述为“从数据流图到NoC平台的映射过程”,即数据节点到NoC平台基本单元Tile的分配过程。

这里需要注意的是,该模型下数据节点的个数一般大于NoC平台的规模,即不同的数据节点可能映射到相同的平台单元上。该映射问题的复杂度已经超越了二次分配问题,而类似于经典装箱问题[2],属于NP难问题。因此不能使用常规算法,而必须使用启发式算法寻求其最优解。

2.2 影响映射结果的关键因素

NoC映射的作用及其意义主要有两个:第一个就是得到一个具体的映射方案,该映射方案确定数据节点交付特定NoC处理器的关系,在实时系统运行于NoC上之前,完成一种静态的任务分配工作;第二个就是通过设定一定的优化目标和约束条件,以获得最优或者接近最优的映射方案,以保证系统运行时能满足一定的性能指标。根据对NoC关键技术的研究成果[1]以及实验结果,影响映射结果的关键因素主要包括以下几方面:

1) 应用系统

显而易见,不同的应用系统对应着不同的数据流图,即产生不同数目的数据节点。应用系统规模越大,映射到相同Tile的数据节点越多,对Tile的处理器处理能力的要求越高;反之对处理器处理能力要求越低,会增加空闲处理器的数目。

2) NoC拓扑结构

不同的网络拓扑结构,导致其路由策略的不同,则应用系统节点间的信息传递延迟也将发生变化,从而导致系统关键链路延迟的变化。同时,网络单元中路由节点、处理器等的运行情况也将有所不同,对于面向延时和功耗的映射过程来说,必将产生不同的映射结果。

3) 采用的映射算法

好的映射算法意味着用更快的速度、更小的计算复杂度完成映射过程,并获得比较好的性能指标。由于映射问题的复杂度非常高,因此选取好的启发式映射算法对于获得更好的映射结果来说至关重要。

4) 优化目标

优化目标是映射算法运行过程中的关键参考值。因为映射算法的每次迭代过程中都将执行一次目标的比较,不同的优化目标将产生不同的算法收敛过程,必定产生不同的映射结果;此外,单优化目标和多优化目标对应的映射过程也是不相同的。

5) 约束条件

约束条件的存在意味着映射过程中不可行解的存在(不满足约束条件的解称为不可行解)。如果约束条件设置得比较宽松,则可行解的个数较多,映射可行方案也增多;如果约束条件设置得比较苛刻,则可行解的个数减少,甚至导致可行解不存在,那么映射可行方案也将减少,甚至不存在。因此,最优映射方案的选取范围大小与约束条件的多少成反比关系,即约束条件越多,选取范围越小;反之越大。

3EDA工具设计

由上一节对影响映射结果的关键因素的描述可以看出来,各种关键因素的不同组合都会带来不同的映射结果。为了帮助研究人员更全面、更方便地获取NoC映射的相关结果,一个可重配置参数的友好的应用仿真界面的设计是非常必要的。一方面,由于本文关于NoC映射的所有仿真语言都是基于Matlab的,并且一些优秀的映射算法如遗传算法[3]在网络上可以很方便地下载到Matlab的工具箱;另一方面,Matlab本身自带的GUI工具是简单易学的图形化用户界面设计工具,设计出来的工具界面美观且易于操作;且最终生成的界面程序可以方便移植到任何电脑上使用。因此,本文采用GUI的一般设计方法完成用于NoC映射的EDA工具设计,并提供下载链接[4]。下面将从软件层次结构和工具特性两个方面具体介绍该EDA工具。

3.1 软件层次结构

由图2,可以看到该工具的组成模块包括:

1) 输入模块

输入模块主要执行两个过程:一个是完成DFG的输入和处理,即初始化给定DFG的节点权值、边权值、连接关系等,然后转化成可供后续模块处理的链路连接信息;二个则是完成NoC拓扑结构构建,即初始化网络结构类型、网络大小、交换延时等,然后转化成可供后续模块处理的路由路径信息。

2) 选择模块

为满足不同研究需求,选择模块用于依次选定具体的约束条件、映射算法和优化目标,并完成相应选项的参数设置,转化成选择输出进入到执行模块。

3) 执行模块

从输入模块得到的链路连接信息和路由路径信息,以及从选择模块得到的选择输出,一起作为执行模块的输入,然后该模块开始运行软件的核心程序,执行映射过程。

4) 输出模块

映射过程结束后,输出模块根据输入模块和选择模块的设置情况,输出相应的映射结果,画出相关曲线,保存仿真信息到文件中。

3.2 工具特性

按照GUI的设计步骤,结合工具的功能要求,笔者完成的NoC映射EDA工具初始界面如图3所示。

可见,该工具各组成部分功能及相关特性如下:

1) DFG信息输入(见图4)

支持手动设置DFG信息或者自动读取DFG信息文件。手动设置需要完成DFG各节点和有向边的权值设置,适用于修改不多、规模较小的应用;读取DFG信息方式,只需要按照默认文件内容的格式输入节点和边的信息,以文本格式保存即可,适用于修改不频繁、规模较大的应用。

支持DFG图形预览。根据输入的DFG信息,使用圆形节点图(即将节点均匀分布在一个圆上)预览DFG,便于用户检查信息输入是否正确。

支持设置输入节点集和输出节点集。

2) NoC拓扑结构选择(见图5)

支持三种NoC拓扑结构的选择:2D-Mesh[5],2D-DeBruijn(以下简称2D-DB)[6]和3D-Mesh[7]。每种结构都可以选择特定的网络大小和设定路由节点的单位交换延时。

3) 映射算法选择(见图6)

支持两种映射算法的选择:随机映射算法和遗传映射算法。任何一种映射算法都有相应的参数设置。

4) 优化目标选择(见图3)

支持延时或功耗的单目标优化以及结合两者的双目标优化。对于功耗目标优化,还允许设置各功耗组成部分的比例,如处理器功耗、路由节点功耗和网络功耗。

5) 约束条件选择(见图3)

对于二维网络拓扑来说支持最多两个约束条件,即注入率(数据到达速率)和水平带宽;而对于三维网络拓扑来说支持最多三个约束条件,即注入率、水平带宽和垂直带宽。约束值可以自行设定。

6) 其他功能与特性

对于所有可设置的参数设置默认值,保证一般用户也可以使用该工具。

由于映射过程具有多次迭代,仿真过程中支持进度显示。

仿真结束生成的仿真结果包括解的集合(即最优映射方案)、收敛曲线、对比曲线等;对于双目标情况还增加三维收敛图。

运行结束后,仿真结果及详细参数设置情况保存到特定文本文件中,便于用户查询,并显示运行总时间。

4仿真应用实例

接下来,我们采用IMT高级无线传输系统[8]中的MIMO/OFDM接收端设计为例,将其应用系统划分成4类模块(A/B/C/D)共32个数据节点。其在单输入单输出(以下简称SISO)和4输入4输出(以下简称4I4O)模式下等效的DFG如图7。

使用笔者设计的工具,采用默认参数设置,完成以下四种映射过程的仿真实验:

1) SISO系统映射到16单元2D-Mesh平台;

2) 4I4O系统映射到16单元2D-Mesh平台;

3) SISO系统映射到16单元2D-DB平台;

4) 4I4O系统映射到16单元2D-DB平台。

假设数据到达率等于30毫秒,带宽约束设为50毫秒,选用遗传映射算法(GA,Genetic- Algorithm),则在映射过程1)下,运行EDA工具得到其收敛曲线如图8所示。

由图8中可见,经过200次遗传迭代之后,最小延时收敛在0.1425秒左右,最小功耗延时收敛在600左右(归一化功耗和值)。同样道理,使用该工具完成其他三种情况下的仿真实验后,通过对仿真信息文件的保存,我们可以得到这四种情况下的延时和功耗收敛对比情况,见表1。

由表1可以得到两个结论:由于4I4O系统具有比SISO更高的并行度,因此SISO的输入输出关键延时最优值要远大于4I4O输入输出关键延时最优值。由于2D-DB网络结构的优越性[5],使用2D-DB网络结构得到的映射优化目标值要比使用2D-Mesh网络结构得到的值更优一些。

另一方面,为了比较映射算法不同带来的映射结果的不同,针对情况1),我们同时采用了随机映射算法(RA,Random-Algorithm)和遗传映射算法,再次运行工具,得到双优化目标的对比图如图9。

图9中,我们使用GA得到的5对映射目标值和使用RA得到的100对映射目标值作对比,显而易见的是,GA得到的所有解均由于RA得到的所有解。表2给出了GA和RA在求解映射问题时的主要区别。

5结论与扩展

本文基于传统NoC映射模型,首先提出了一种从数据流图到NoC平台的映射模型,并详细讨论了不同映射条件对映射结果的影响。然后结合这些影响因素,采用Matlab中通用GUI的设计方法,设计出一款速度快、操作便捷、界面友好、可重配置、能存储详尽仿真信息、获取发丰富仿真结果的NoC映射设计工具,从而进一步提高了NoC映射研究的效率。该EDA工具若能继续丰富各种选项,如添加其他网络拓扑结构、更多映射算法等,必将进一

步简化NoC映射的研究工作,使研究人员能更直观、更便捷地得到很高参考价值的实验数据和图表,从而大大推动NoC基础研究的步伐。

参考文献

[1] 谭耀东,刘有耀.NoC系统研究综述.[J].西安邮电学院学报,2008,13(1):5-9.

[2] Falkenauer, E., Tapping the full power of genetic algorithms through suitable representation and local optimization : application to bin packing, in Evolutionary Algorithms in Management Applications, pp. 167-182, Spring-Verlag, Berlin, 1995.

[3] Zhao Man; Tan Wei; Li Xiang; Kang Lishan; Research on Multi-project Scheduling Problem Based on Hybrid Genetic Algorithm. Computer Science and Software Engineering, 2008 International Conference on.Volume 1, 12-14 Dec. 2008 Page(s):390-394

[4]teacher.uestc.省略/Thome/Hujh/Course/1246591381.rar

[5] Sabbaghi-Nadooshan, R.; Modarressi, M.; Sarbazi-Azad, H.; The 2D DBM: An attractive alternative to the simple 2D mesh topology for on-chip networks. Computer Design, 2008. ICCD 2008. IEEE International Conference on.12-15 Oct. 2008 Page(s):486 - 490

[6] Mohammad Hosseinababy, et. al., Reliable Network-on-chip Based on Generalized de Bruinj

(下转第81页)

Graph, IEEE international High Level Design Validation and Test Workshop, 2007, pp. 3-10.

[7] Huaxi Gu; Jiang Xu; Design of 3D Optical Network on Chip. Photonics and Optoelectronics, 2009. SOPO 2009. Symposium on.14-16 Aug. 2009 Page(s):1 - 4

[8] Chuanxue Jin, the Down-link Design for the B3G System, master dissertation of the university of electronic science and technology of china, 2006.

作者简介

陈庚生,硕士生,专业为通信与信息系统;

陈亦欧,博士生,专业为通信与信息工程;

胡剑浩,教授,博士生导师,主要从事无线通信和VLSI的研究。