赵广佩 曾宪彬

杭州电子科技大学通信工程学院，杭州 310018

引言

随着半导体技术和集成电路产业的发展，嵌入式系统硬件的功能越来越强，支持的应用范围也越来越广，其核心处理器的频率也是越来越高。虽然随着处理器频率的增高，系统性能也在提升；但是这也带来了一系列的问题，比如：能耗、线干扰和线延迟等。而这些问题已严重影响了嵌入式系统性能的提高，因此，在嵌入式系统设计中使用多处理器片上系统（MPSoC: Multi-Processor System-on-Chip）已经成为未来的一种趋势[1]。另外，由于嵌入式系统是“嵌入到对象体系中的专用计算机系统”，它强调的是面向具体应用的性能最优，而MPSoC的片上存储器与其面积、能耗、性能等几个关键因素直接相关，并且已经成为嵌入式系统性能提升的瓶颈[2]。因而，如何设计嵌入式MPSoC的片上存储器，使得它对具体应用最优，已经成为一个亟待解决的关键问题。

1 片上存储器的构成

片上存储器是嵌入式存储系统中一个至关重要的层次，它主要是为解决处理器和片外存储器之间速度不匹配的问题而设计的。图1给出了嵌入式存储系统的层次结构。

从图1中可以看出，沿着存储层次自顶向下，存储器的单位成本降低，存取时间增大，存取能耗增大，访问频度降低，容量增大。寄存器处在最顶层，位于处理器内核中，提供最快的存储访问速度。接下来一层仍然在芯片内部，主要包括SPM(Scratch-Pad Memory)和Cache两种，这一层就是本文要重点研究的片上存储器。再往下就是板级存储器，可以分为主存和掉电非易失存储器两层。采用这种层次性结构，可以用低速、高能耗存储器的平均价位得到高速、低能耗存储器的性能，并能满足系统对存储器容量的要求。

从图1中可以看出，嵌入式片上存储器主要包括SPM和Cache两种结构；其中，SPM由基本的SRAM构成，Cache是内部的高速缓存，它们在嵌入式系统的位置如图2所示。

从图2中可以看出，Cache位于处理器内核和主存之间，不占用独立的地址空间。Cache从局部性原理考虑，保存最近一段时间内处理器访问到的主存内容，这样就可以减少外部低速存储器的访问，并且也能降低能耗。处理器在需要进行数据指令读取操作时，总是从Cache中读取，根据地址检查是否命中。如果命中，则直接将数据或指令传送给处理器；否则就先从主存储器中把所需内容送入Cache，然后再送给处理器。

图1 嵌入式存储系统层次结构图

图2 Cache和SPM在嵌入式系统中的位置

表1 Cache和SPM的比较

SPM通过片上高速总线和处理器直接连接，独占一段地址空间，保存着部分指令和数据。当处理器需要进行指令数据读取时，首先根据访问地址判断地址空间，选择SPM或主存。前者可以直接操作，后者则需要通过外部存储器接口模块来访问，并且需要时序上的等待和片外总线驱动等，极大地影响了速度并增加了能耗。Cache和SPM的比较如表1所示。

通过上表中的对比可以看出，Cache和SPM各有优缺点。Cache的控制和访问是自动完成的，不需要通过软件进行管理；但是其能耗和面积较大，并且在数据未命中时的访问时间是不确定的。相反，SPM需要通过软件进行管理；但是其能耗和面积较低，并且访问时间确定。因此，在设计嵌入式MPSoC的片上存储器时，为了取得更好的系统性能，可以对Cache和SPM进行综合设计优化。

2 Cache设计优化技术

Cache即高速缓冲存储器，它根据数据局部性和程序局部性，把正在执行的指令地址附近的一部分指令或数据从主存装入Cache中，供处理器在一段时间内使用；这样就可以减少对片外存储器的访问，进一步减少处理器的处理时间，提高系统性能。

对Cache的设计优化，首先可以优化它的结构参数。Cache的主要的参数有容量、行大小、写策略、替换算法和映射方式。Milenkovic等人[3]基于ARM处理器的不同Cache参数配置，采用Mibench作为基准测试程序，对统一Cache和分离Cache进行直接映射和关联映射下的参数配置，同时还更换替换算法(pLRU、LRU、FIFO和Random算法)，以及改变Cache的容量大小，最终得到在不同应用下的不同优化结果，为Cache设计提供依据。

除了上面提到的设计优化一些Cache参数外，也可以从程序编译信息方面出发来进行Cache的设计优化。[4,5]分别从指令和数据的角度出发，来降低Cache的丢失率。[4]需要首先将程序执行一遍，预先获取程序执行流，然后根据这些执行轨迹避免Cache冲突，以降低Cache的丢失率。[5]在2008年提出了一种Cache对数据的动态管理方法，通过该方法可以减少了片外的访问，提高了Cache的命中率。

另外，在优化Cache的硬件结构设计优化方面，在2009年，[6]基于降低Cache能耗的问题，提出了一种减少Tag位数的方法。另外，Alipour[7]在2011年通过探索设计Cache的空间大小，从而针对具体应用在系统上获得了最佳的性能/能耗比。

总的来说，Cache设计在嵌入式应用中的研究可以分为两个方面：一方面是通过修改Cache的组织结构和工作机制，增强对应用程序的处理能力；另一方面是对软件的编译过程进行控制，使得优化后的目标程序，能够提高Cache的利用效率。

3 SPM设计优化技术

相比于Cache，SPM由于在面积、能耗和实时性等各方面的优势，使得它在嵌入式芯片中应用越来越广泛，而合理有效的使用SPM也已经成为了嵌入式MPSoC片上存储器设计与研究的热点问题。而基于SPM进行性能和能耗优化的关键问题在于，对于有限的SPM空间，如何确定哪些内容存入其中，从而最大限度地提高软件的运行速度。

3.1 SPM静态设计优化技术

Sjodin[8]在1998年提出了通过静态解析应用程序，分析各个全局数据变量的执行次数，将频繁访问的全局数据变量置入SPM的分配方法。该方法可以减少片外的访问，提升系统性能，但由于文中只优化了全局变量并且采用的分配算法是简单的首次适配算法，因此它在优化后并不能得到最高的SPM利用率。

Oren等人[9]在2001年提出了一套基于链接器使用0/1整数线性规划算法的SPM优化技术。它根据程序运行记录确定各全局数据变量和函数堆栈的读写次数，然后计算全局数据变量和函数堆栈中变量对性能的影响值，借助Matlab中0/1整数线性规划算法工具挑选适当变量放入SPM，最后通过链接器直接生成可运行的程序。2003年，文献[10]在他们研究的基础之上，又加入了对大型数组进行划分的策略。

Koc等人[11]在2007通过数据的重计算，提出了一种SPM空间优化策略，目的是减少片外存储器的访问次数。文中通过多个测试程序对提出的算法进行了实验仿真；实验表明，通过文中提出的算法对SPM进行空间优化，可以得到大约10.8%的系统性能提升。

除了上面这些软件方面的优化，Angiolini等人[12]提出了一种SPM静态布局优化技术的硬件架构。该技术在硬件架构上增加了一个指令译码器，以确定是从SPM中还是从Cache中取指令。该技术直接作用于包含符号表信息的二进制代码，无需编译器也无需源代码。由于静态方法对代码的分配比较有效，所以文中仅针对代码进行了分析，没有对数据进行分析。

由于上述SPM设计技术中分配到SPM中的数据在程序运行过程中是不变化的，因此这种方法被称之为静态分配方法。近年来，随着研究SPM动态设计优化技术的热潮的兴起，对SPM静态设计优化技术的研究逐渐变少。

3.2 SPM动态设计优化技术

上一小节提到SPM静态布局优化技术无论是采用程序分析还是借助编译器驱动，分配到SPM中的数据在程序运行过程中都是不变的，都没有考虑SPM中对象的时间有效性。这在很大程度上限制了SPM的使用率，特别是当SPM容量有限时，一部分高频访问的指令和数据将不得不被置于片外存储器中。所以，近期的研究提出了一些SPM动态设计优化技术。

Steinke等人[13]在2002年提出了动态复制指令至SPM的能耗优化方法。该算法根据文中提出的两个假设可以得到了可供优化的集合，然后再利用模型仿真确定最终的优化集合。该方法也有自己的缺陷：首先它的研究对象局限于循环指令代码段，而没有综合考虑数据、变量等因素；其次它只考虑了循环，而没有考虑其它影响执行频度的因素，诸如无条件跳转，条件分支等。针对以上缺陷，Verma等人[14]在2004年提出的优化策略中，分析了全局变量、局部变量、指令代码段，但是没有考虑到非连续对象之间跳转对对象能耗和体积的影响。

由于利用编译器很难对一些不规则的访问进行优化，针对这个问题，文献[15]在2008年提出了一种利用马尔科夫链的基于数据访问预测的SPM动态管理方法。该方法主要针对那些不易被编译器优化的非规则的访问，比如：指针访问、索引数组访问等。

另外，在2010年文献[16]提出了一种在运行时把最佳的代码段映射到SPM中的编译器驱动方法。该算法基于一个贪婪的成本模型，使用编译器识别程序中的热点；并且利用DMA方式传输到SPM中，而不是通过处理器显式装载和存储。但是该算法的优化只针对的是程序中的热点，而没有对数据进行优化。

Salamy[17]在2012年提出了一种综合任务调度和SPM数据分配的优化算法。在嵌入式MPSoC中，多核间的任务调度和片上存储器的数据分配是两个关键问题，本文把这两个问题结合起来对系统进行了优化，可以更好的提升SPM的利用率。

上述动态管理SPM的研究主要基于对算法和编译器的优化，但在MPSoC的片上存储器设计中，单纯使用软件方法所获得的优化效果是有限的。因此，同时从硬件架构和软件策略两个方面对SPM进行优化是研究的趋势。

Hyungmin[18]在2007年提出一种基于MMU的SPM动态管理机制，他们对数据、代码和堆栈进行优化。但是文中对数据、代码和堆栈分开考虑，未能对整个程序进行优化。另外，文中强调了数据和代码的局部性，却没有考虑堆栈访问的局部性。而这些都是可以进一步研究的问题。

Doosan等人[19]在2009年，针对多媒体应用，通过数据的可重用性提出了一种结合软件（编译器和操作系统）和硬件（数据访问记录表）技术的综合优化算法。文中通过编译器分析生成数据布局和跟踪动态内存访问的硬件组件，高速缓存的数据布局可以应用于一个输入数据模式，该布局技术要在OS中高速缓存运行时的内存管理器帮助下完成。本文中运用的数据分配策略利用了动态应用程序，可以实现高效的高速缓存。

由于SPM动态设计优化技术具有很好的动态性，可以很好的保持SPM的高效率，所以，近年来一直是SPM相关问题的研究热点。另外，在近年来的一些研究中，也常常综合考虑SPM动态设计技术和静态设计技术来进一步提升嵌入式MPSoC的系统性能。

4 SPM和Cache共存时设计优化技术

虽然Cache的使用使得嵌入式MPSoC系统，特别是面向多媒体的应用系统，在速度上有了很大的提升，但它却使得芯片消耗更多的能耗和面积，特别是在实时应用中Cache更是难以胜任。与Cache相比，SPM在能耗、面积和实时性上有所改善，但是需要程序员对代码布局进行精心安排来优化SPM的作用。因此，在近期的研究中，一些研究人员已经开始在MPSoC中采用SPM和Cache协同工作的方式来优化嵌入式系统性能了。

在SPM和Cache共存的嵌入式MPSoC系统中，所面临的问题是：某个嵌入式应用程序编译后的程序数据可以安排在SPM中，也可以安排在片外存储器中；而如何安排这些数据的位置，才能最大程度提高程序的性能，这便是SPM和Cache共存时的片上存储器设计优化技术所要研究的问题。

Kandemir等人[20]在2001年提出了一种动态的SPM和Cache数据划分的方法。该方法根据程序访问成组数据的记录信息，将成组数据划分成块，然后在指定时刻，再从存在竞争的数据块集合中选择一些复制到SPM中。

2005年，针对文献[20]提出的方法，Abstar等人[21]建立了更为复杂的分析模型并提出了一套新的用于描间接索引方式成组数据的框架，用于在适当时刻将这类成组数据的关键部分复制到SPM中。为了减少代码的修改，在文中的硬件框架中，SPM中的数据是通过DMA从片外存储器中输入。

在实际的使用中，充分发挥SPM和Cache共存架构的优势的关键在于如何划分代码或数据，使得两种片上存储器更能发挥自己的优点，所以对程序的划分算法显得尤为重要，Verma[22]为此提出了一种分配算法，文中认为对Cache进行SPM辅助优化的首要问题是得知哪些代码在运行时会产生Cache丢失；因此，文中在代码运行时进行跟踪，并通过生成冲突图表来描述Cache的行为。

在SPM和Cache共存时，通常是采用以SPM优先优化代码的布局，然后才考虑到Cache的作用。这是因为Cache对程序员而言是不可见的，在对Cache进行软件优化时需要花费大量的工作，文献[23]便是这种研究方式。该文献在SPM和Cache共存的系统中提出了一种如何把程序和数据分配到SPM上的策略，文中通过直接分析应用的二进制代码，然后在其中插入指令实现片外和片上的跳转，提高了SPM的利用率，另外还可以针对具体应用获得最佳的Cache容量。

现有的混合缓存虽然提供了Cache和SPM的灵活分区，但没有考虑运行时缓存的自适应性；并且之前的缓存设置平衡技术要么能源利用率低要么需要串行tag和数据数组访问。针对这个问题，Jason等人[24]于2011年提出了一种自适应混合Cache技术，该技术可以让SPM块动态地从高需求Cache区向低需求Cache区进行地址重映射。文中通过重新配置部分Cache作为软件管理的SPM，使混合Cache可以实现同时处理未知的和可预测的内存访问模式。

总之，合理选择并设计片上存储器架构，动态划分Cache和SPM，并对其算法进行优化以减少内核访问外存的次数，是嵌入式片上存储器设计优化的关键，也是几个重要的研究方向。因为，这些问题直接关系到嵌入式MPSoC的性能、成本和能耗。

5 结语

由于嵌入式MPSoC的片上存储器与其面积、能耗、性能等几个关键因素直接相关，并且已经成为系统性能提升的瓶颈。所以，如何设计嵌入式MPSoC的片上存储器，已经成为一个亟待解决的关键问题。本文针对这个问题，详细地介绍了近十几年来嵌入式MPSoC片上存储器设计优化技术的相关研究。文中，在介绍了嵌入式MPSoC的两种片上存储器SPM和Cache之后，首先对Cache的一些软硬件设计优化技术进行了详细的综述；然后针对SPM，本文分别按照SPM静态设计优化技术和SPM动态设计优化技术进行了综述性的介绍；最后对SPM和Cache共存时的设计优化技术进行了介绍和总结。另外，本文还在综述和介绍的基础上讨论了当前嵌入式MPSoC片上存储器的研究热点问题，并对未来的研究方向和发展趋势进行了展望。

[1]Wayne Wolf. The Future of Multiprocessor Systems-on-Chips[C]. Proceedings of the 41st Annual Design Automation Conference，2004：681-685

[2]Ozturk O，Kandemir M, Irwin M J，et al. Multi-Level On-Chip Memory Hierarchy Design for Embedded Chip Multiprocessors[C]. 12th International Conference on Parallel and Distributed Systems，2006

[3]Milenkovic A，Milenkovic M，Barnes N. A Performance Evaluation of Memory Hierarchy in Embedded Systems[J]. Proceedings of the 35th Southeastern Symposium on System Theory，2003：427-431

[4]Pararneswaran S，Henkel J. Instruction Code Mapping for Performance Increase and Energy Reduction in Embedded Computer Systems[J]. IEEE Transactions on Very Large Scale Integration Systems.2005，13(4)：498-502

[5]Molnos A M. Heijligers M J M，Cotofana S D. Compositional, Dynamic Cache Management for Embedded Chip Multiprocessors[C]. Design，Automation and Test in Europe，2008：991-996

[6]Ji Gu，Hui Guo，Li P. ROBTIC：An On-chip Instruction Cache Design for Low Power Embedded Systems[C]. 15th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications，2009：419-424

[7]Alipour M，Moshari K，Bagheri M R. Performance per Power Optimum Cache Architecture for Embedded Applications，A design Space Exploration[C]. 2011 IEEE 2nd International Conference on Networked Embedded Systems for Enterprise Applications，2011：1-6

[8]Sjodin J，Froderberg B，Lindgren T. Allocation of Global Data Objects in On-Chip RAM. Compiler and Architecture Support for Embedded Computing Systems，1998

[9]Avissar O，Barua R，Stewart D. Heterogeneous Memory Management for Embedded Systems[C]. In the Proceedings of the 2001 intemational conference on Compilers，architecture and synthesis for embedded systems，2001：34-43

[10]Verma M，Steinke S，Marwedel P. Data Partitioning for Maximal Scratchpad Usage[C]. In Proceedings of the Asia and South Pacific Design Automation Conference，2003：77-83

[11]Koc H，Kandemir M，Ercanli E，et al.Reducing Off-Chip Memory Access Costs Using Data Recomputation in Embedded Chip Multi-processors[C].44th ACM/IEEE Design Automation Conference，2007：224-229

[12]Angiolini F，Menichelli F. A Post-Compiler Approach to Scratchpad Mapping of Code[C]. CASES 2004

[13]Steinke S，Gmnwald N, Wehmeyer L. Reducing energy consumption by dynamic copying of instructions onto onchip memory[C]. In proceedings of the 15th International Symposium on System Synthesis，2002：213-218

[14]Verma M，Wehmeyer L，Marwedel P.Dynamic Oveday of Scratchpad Memory for Energy Minimization[C]. In the Proceedings of the 2nd IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis. 2004：104-109

[15]Yemliha T，Srikantaiah S，Kandemir M，et al.SPM management using Markov chain based data access prediction[C]. 2008. IEEE/ACM International Conference on Computer-Aided Design，2008：565-569

[16]Hongmei Wang，Lei Shi，Tiejun Zhang，et al.Dynamic Management of Scratchpad Memory Based on Compiler Driven Approach[C]. 2010 3rd IEEE International Conference on Computer Science and Information Technology，2010：668-672

[17]Salamy H，Ramanujam J. An Effective Solution to Task Scheduling and Memory Partitioning for Multiprocessor System-on-Chip[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems，2012，31(5)：717-725

[18]Hyungmin Cho，Bernhard Egger, Jaejin Lee，et al，Dynamic Data Scratchpad Memory Management for a Memory Subsystem with an MMU. LCTES'07，2007

[19]Doosan Cho，Pasricha S.，Issenin I.，et al.Adaptive Scratch Pad Memory Management for Dynamic Behavior of Multimedia Applications[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems，2009：554-567

[20]Kandemir M，Ramanujam J，Irwin M.J，et al. Dynamic management of scratch-pad memory space[C]. In Design Automation Conference，2001：690-695

[21]Absar M J，Catthoor F. Compiler-Based Approach for Exploiting Scratch-Pad in Presence of Irregular Array Access[C]. In Proceedings Design，Automation and Test in Europe，2005：1162-1167

[22]Verma M，Wehmeyer L，Marwedel P，et al.Cache-Aware Scratchpad Allocation Algorithm[J]. IEEE Transactions on Computer-Aided Design of Integrate Circuits and System，25(10)，2006: 2035-2051

[23]Ling Ming，Zhang Yu，Shen Lin. An Alternative Choice of Scratch-Pad Memory for Energy Optimization in Embedded System[C]. IEEE International Conference on networking, Sensing and Control，2008：1641-1647

[24]Cong J，Gururaj K，Hui Huang，et al. An energy-efficient adaptive hybrid cache[C]. 2011 International Symposium on Low Power Electronics and Design，2011：67-72