基于反馈的片上多处理器系统层次负载平衡算法

针对现有负载平衡算法未能有效利用片上多处理器系统线程级并行性,没有考虑线程间数据共享与通信以及产生颠簸等问题,提出了一种基于反馈的层次负载平衡算法.采用层次式调度,将属于同一进程的多个线程静态调度到特定规模的内核子集上,并在此基础上根据系统实时负载情况在特定内核子集内动态迁移线程,以降低同一进程的多个线程之间的通信代价.在线程迁移过程中,引入反馈机制,即以系统颠簸情况为反馈信息,实时调整迁移数目,最终使系统较快地达到平衡.实验表明,基于反馈的层次负载平衡算法能使系统的平衡程度达到较高的水平,引入的反馈机制可使系统平衡速度提高 28%,并在系统平衡前使"颠簸"数目减少 54%.     

网格结点选择中基于时间模型的多起点最陡爬山算法

为任务计算时间和任务间通信时间构建一个运行时间模型，根据资源性能相对差异，模型可从一种结点选择下的任务计算和任务间通信时间，计算出其他结点选择下的任务计算时间和任务间通信时间．基于运行时间模型实现的多起点最陡爬山算法，分别在多个潜在收敛域选择搜索起点，使搜索结果更优．该模型预测任务计算时间、结点内任务通信时间、结点间任务通信时间和应用总运行时间的平均误差分别为17％、19％、15％和11％，实验表明，该算法可有效提高应用性能．     

校园级元计算系统的一种多级对象命名方法研究

为了促进元计算系统的实现效率,提高扩展性,提出了分布式对象的一种多级层次命名方法,阐述了基于Internetr的元计算系统的分布式对象模型（WOM）的组织结构,提出了WOM的4级对象命名方法,并给出了WOM的各级对象标识符的定义,4级层次对象命名方法是广域分布式环境（WADE）系统的核心技术之一,它有利于元计算系统的扩展和伸缩,促进WADE系统的灵活实现,实验表明,WOM支持的对象通信效率可以提高25%左右。     

用伪二叉树法则构造多目标Pareto最优解集的方法

针对多目标进化算法中如何提高非支配集构造效率的问题,提出了一种用伪二叉树法则构造多目标Pareto最优解集的方法.根据多目标解的性质,将解的比较结果分为支配、被支配以及不相关3种类型,再根据解的比较结果生成排序伪二叉树.在每一轮比较中,从进化群体中选出一个个体,将该个体与当前非支配集中的个体进行比较,淘汰被支配的个体,而未被淘汰的个体将插入到非支配集中第一个被淘汰个体的位置.依次进行,直到进化群体中的个体比较完毕,从而生成排序的伪二叉树.同时,在理论上证明了采用该方法获取的非支配集为目标进化群体的最大非支配集,分析得知其在最差情况下的时间复杂度为O(rN2/2).实验结果表明,当目标数较大时(r≥5),在构造非支配集的效率上伪二叉树法要明显优于Deb、Jensen算法及擂台赛法则.     

网环步进码片上网络自适应路由算法设计

针对片上系统使用过多虚拟通道带来大量的缓存面积及能耗开销问题,提出了一种网环步进码(TSC)片上网络自适应路由算法.将网环网络中2个虚拟通道划分为按编码"O"或"1"数量递减或者递增的2个子网络,按TSC编码为网环拓扑结构中的网络节点进行编码,每个节点与相邻节点有且仅有一位不同,由此可以减小网络开销,避免片上死锁.实验结果表明:在均匀传输模式下,算法可为94%的数据包提供自适应路由选择,并在不增加虚拟通道数量的前提下,提高路由算法在网络负载增大时的适应能力.     

面向Pareto最优遗传算法的服务组合方法

为了解决Pareto遗传算法在每一次进化操作中都要构造当前进化群体最优解集而影响运行效率的问题,提出了一种面向Parfto最优遗传算法的服务组合方法,以实现Web服务组合的全局优化.用伪二叉树法则构造目标函数的Pareto最优集合,再进行Pareto最优解集排序,最后采用个体相似度计算来确定遗传算法的适应度函数,由此获得一组满足约束条件的Pareto最优解服务集合.实验验证表明,所提方法可以提高多目标遗传算法处理服务组合效率的问题,即使在服务规模较大的情况下,所获得的解与最优值的比率仍能接近90%的水平.