一个面向异构多核处理器Cell的资源分配模型

处理器

高技术通讯 2 1 00年第 2 0卷第 1期：29~13 2 12 24di 1 3 7/ . s 1 0—4 0.0 0.2.0 o:0.7 2 j i n.0 20 7 2 1 1 O 4 s

一

个面向异构多核处理器 C l的资源分配模型① el王森② 王志英③邬贵明(防科学技术大学计算机学院长沙 4 07 )国 10 3

摘

要

为了充分利用多核处理器提供的多级并行和解决多核资源分配问题，出了一提

种将多任务并行程序映射到多核处理器平台上的模型驱动的方法。该方法首先创建一个三维优化空间来表示资源分配配置，而后通过搜索该空间为应用生成多种并行机制，后最对各种并行机制进行静态评估从而找出最优的机制。该方法同时考虑了任务并行、数据

并行以及通讯开销。在异构多核处理器 C l上利用一个图像处理应用对此方法进行了测 e l试。实验表明，种模型驱动的方法能够很好地评估性能并为应用确定有效的并行机制。这

关键词多核处理器，资源分配模型，S型， B P模任务并行，据并行数数据局部性，时也不能准确地估算通讯代价。其 同它工作[主要关注多核代码自动生成技术，括 ],包开发 C l的线程级并行及单指令多数据 (i l i. e l s g n ne sut nm lp a,I ) t c o u il dt SMD并行。 r i te a与以上工作不同，文提出了一个资源分配模本

0引言 在单芯片上集成多个处理器核已成为当前处理器设计的主流。S IS N T S IA和 IM) T (O Y、 O H B B联合开发的 Cl e l宽带引擎 ( e r d ad E g e C l C l Bo bn ni, e l a n l

型 (e uc lctnm dlR A,模型综合考虑 rs r aoao oe, s )该 o e l i了多级并行及通讯代价。R A主要基于整体同步并 S行 (uksnhoos a l lB P模型l在 R A中， b l cr u r l, S ) y n p ae, S一

B )l多核处理器的代表，是目前学术界最为 E _是 j也关注的异构多核处理器。C l B e E包含一个 Pw rC l o eP 核 ( o e处理器 (o e r es ge m n, P )和

8 pw r pw r o s n l et P E ) pc i e个向量协处理器 ( yeg t rcs n l e t, snr sc poes g e m ns ii i e

个多任务程序被抽象为一系列的计算步和通讯

步，个计算步集合了可以并行执行的任务，个通每每讯步传输相邻计算步间的数据。每个任务的数据并

SE, P P ) P E运行操作系统， P S E执行计算密集型任

务。每个 SE拥有 26 B本地存储，P P 5K SE通过内部总线与主存或其它 S E进行数据传输。近期的研 P究 l3实 C lB 2’证 J e E具有很强的计算能力。 l

行由一个源到源编译器开发 _。为了获得多任务程 8 J序的最优并行策略， S R A建立了一个三维优化空间， 并通过搜索该空间来为程序得到高效的并行机制。我们在 S n布的基于 C l处理器的 PaS tn3 oy发 e l l t i y ao平台上，利用 R A对图像处理应用 Sb l行测试。 S oe进

然而，何利用 C l的并行计算能力给程序员如 e l带来了很大的挑战。首先，核上的计算资源和存多储资源需要进行显示管理。其次，用程序的并行应计算部分需要分配到 S E上进行运算， P如何充分开发多层次并行，同时减少通讯，仍是并行程序设计人员需要考虑的问题。针对以上问题，多科研机构众及生产商致力于为 C l开发新的编程模型和软件编 e l程环境来减轻编程负担。B ln等 _提出了 C l s e es 4 l J e S l用于开发程序的任务并行， e S基于一个源到源 C Cl s l编译器和一个运行时系统，行时系统负责任务及运

实验表明， S R A能很好地进行性能评估，能为应用并确定最优的并行机制。

1问题陈述 给定一个多任务并行程序 P程序中的每个任，务对应于一个数据并行的计算密集型函数。程序 P可以被抽象为一个有向无环图 ( i c d ayl d et cc c r e i

数据的调度。Bao v l j i l提出了 M P模型来 g e c等 J MG处理多核处理器的多级并行，而 M P没有考虑然 MG①②③ 93计划 (0 7 B 190资助项

目。 7 20 C 300 ) 女，9 1年生，士生；究方向：核编译及代码生成。 18博研多 通讯作者， . a: ag i@nd.d .n E m i w nma l o uteu c (稿日期：0 90—1收 20—82 )

gah A )又称任务图，为 G(,。其中， rp,D G,记 V E)结点∈ V表示 P中的一个任务， (,∈ E表示边 U )

-

-—

—

1 9 — 22 - -—

处理器

高技术通讯

21 00年 1月第 2 2 0卷第 1 2期

任务 u与任务之间存在数据依赖关系，即任务使用由任务 u定义的数据。基于 B P模型， S我们将程序 P的任务图 G映射到 C lB e E上， l以下四个方面因素会影响并行策略的选择： 根据 A al律]当并行化一个任务时， mdh定，

算步，两个计算步之间通过通讯进行数据重新分布。图 2 a的并行策略最大化地利用了数据并行， 2 ()图

()的策略同时开发了任务并行和数据并行， b中但却引入了通讯开销。为了确定多任务应用的有效并行机制，我们基于 C l建立了一个资源分配模型， e l该模型考虑了单任务的数据级并行以及多任务应用的任务级并行，够很好地为应用确定最优的并行策略。能

性能提升是受限的；

需要充分利用计算资源来保持并行任务间为单个任务分配更多的计算资源会限制可

的负载平衡；

2单任务数据级并行开发给定一个任务， I￣I我" L f用一个源到源编译器 _ l 8 J

并行执行的任务数；

数据并行会减少可利用的存储资源，也会引

入额外的通讯。

来开发任务的数据级并行，任务生成单程序多数为据 (ig r r ut l dt,P s l po a m lpe a S MD)行代码。首 n e gm i a并

考虑到以上几方面，一个多任务应用确定最为优的多级并行策略并不简单。图 1显示了一个三任务程序的任务图。图 2显示了基于 B P模型将图 1 S中任务图映射到 C l上的两种并行策略。图 2中的 e l

先，编译器利用仿射图__射图划分来计算程序】及仿 o中数组维数间的对齐关系。其次，据数据对齐结根果，编译器对程序中的数组进行按

块划分，将划分并后的数组分配到不同 S E的局部存储中。最后， P编

cm表示 B P模型中的计算步，o n表示通讯步， op S cl l n 虚线箭头表示数据重用，线箭头表示数据传输。实 在图 2 a的并行策略中， () 3个任务对应 3个计算步，

译器为程序插入通讯 (,ht如 si操作 )使得每个 SE f, P能够通过远程访问获得其计算所需但在其他 S E P

每个任务中的数据被分布到 4个 SE上，邻计算 P相步间进行数据重用。在图 2 b的并行策略中， ()任务

上的数据。编译器能够根据不同数据划分以及不同S E数， P为单任务生成不同版本的 S MD代码。对 P

tI和 t k对应第 1 a( so a l s个计算步，任务中的数据每个分别被分配到 2 SE中，个 P任务 t k对应第 2个计 a’ s

于任务的一个 S M P D代码版本，们称之为一个变我元 (a at。图 3 vr n) i显示了单任务 cd oe的变元生成过程。我们利用<cd,D S,, P oe D S E>表示任务 c e d o 的一个变元，即任务 cd在数据划分机制 ( a i oe dt ds a .tb tnshm ) D S,P r u o e e为 D S E数为时的一个 S M i i c PD

代码版本。一个变元具有以下几个属性：

图 1任务图

执行时间；

每个 S E的存储访问空间； P 数据划分机制及所使用的 S E数。 P

S E0 P

S E2 P c mp o

萋薰萋萋c om m

e mp o

∞ mm

cmp o

蓦一罾 鐾c mp ocom m

图 3变元生成

z, mp o

…… 此处隐藏：12903字，全部文档内容请下载后查看。喜欢就下载吧 ……