文档介绍：多核软件设计——动态调度算法实验报告
华南理工大学陈虎博士
tommychen74@
一、问题描述
目前,随着微处理器中晶体管数量的持续增长,单芯片多处理器(即多核)越来越流行。与仅在单处理器上的指令级并行开发相比,多核的开发能够获得更高的性能以及更低的功耗。
许多商业上的多核处理器如SUN公司的T1,Intel公司的E7300系列以及AMD的多核等,-UMA(cache-coherence Unified Memory Access)架构的。在此架构中,每个处理器内核都有自己的L1 cache, 并且共享L2 cache。而Cache一致性机制则由硬件通过监听或目录访问协议实现。
如此一来,多核处理器可以共享物理或虚拟内存空间,利用多线程实现数据的交换与通信。并且Windows、Linux这些操作系统为多线程编程提供了线程创建和同步互斥等原语。因此,许多编程者都可以在多核平台上利用多线程模型开发并行应用程序。然而如何在多核平台上编写出高性能的并行程序(特别是不规则算法程序)却成为一个普遍的难点。
多核编程存在着几点问题:
第一点,编程者如何设计一个能充分利用多线程并行来提高应用程序性能的合适模型。如果没有统一模型,则每个程序都要重新实现多线程的性能提高模型,降低了编程效率;
第二点,并行编程将会不断调用操作系统原语,但是即使对于一名有经验的开发人员,在源代码中插入大量的pthread_create() 和 pthread_mutex_lock()这些线程产生与同步互斥函数,将会导致程序冗长以及易出错;
第三点,随着处理器数目的增加,负载均衡就成了一个很大的问题。而且对于一般的编程人员来说,实现一个动态调度器来解决不规则任务问题来使程序保持在一个良好状态是困难的以及耗时的。
因此,本实验为了解决以上多核编程的问题,开发了一个多核编程模型和相关类库,目的在于减轻开发人员负担,利用此模型接口便可轻松的实现高性能的多线程并行程序,为广大编程者在多核平台上编写并行程序提供了灵活、方便的框架。
在我们的模型中,用户仅需关注自己程序的函数实现以及数据划分,而模型中的调度器则提供了创建线程、动态调度线程以适应不规则算法等功能。我们将会在该报告的以下内容中通过多个实验来介绍该并行编程模型以及编程接口与实现。
二、数据结构
1、任务单元task unit
任务单元是实验模型中最基础的单位,主要由以下数据构成:
typedef struct task_page
{
int cmd; //the func_num that the task execute
void *common_para; //the content needs to process in this task
} task_unit;
mon_para则是应用程序需要传递的内容。
2、缓冲池 buf_pool
缓冲池也称任务池,是任务存储的地方,其中函数包括写缓冲、读缓冲、注册函数等功能,也是线程读取、插入任务的地方。其主要数据构成有:
class buf_pool
{
private:
task_unit *head; //指向首任务的指针
int buf_id; //缓冲池 id
int curr_num; //当前拥有线程数
…
public:
task_unit *ReadBuf();
int WriteBuf(void *user_data);
int WriteBufCmd(int cmd, void *user_data);
void RegisterCallBack(func_model * fp, int index);
…};
3、调度器 Scheduler
缓冲池也称任务池,是任务存储的地方,其中函数包括写缓冲、读缓冲、注册函数等功能,也是线程读取、插入任务的地方。其主要数据构成有:
class buf_pool
{
private:
task_unit *head; //指向首任务的指针
int buf_id; //缓冲池 id
int curr_num; //当前拥有线程数
…
public:
task_unit *ReadBuf();
int WriteBuf(void *user_data);
int WriteBufCmd(int cmd, void *user_data);
void RegisterCallBack(func_model * fp, int index);
…};
三、算法描述
本算法属于调度器对于程序状态判断以及如何分配线程的策略
算法步骤:
1、获取当前各缓冲池的利用率以及增长值:r1, r2...rn,