行、列重路由约束下VLSI阵列重构算法研究

摘要

二维网状结构连接的处理器阵列是一种高效的、被广泛应用于并行处理的多核体系结构，并且由于其简单、规整的内部结构以及良好的可扩展性，使得它可以高效、快速地处理图像、信号等复杂的数据。然而，随着超大规模集成电路工艺和技术的不断发展，单一芯片上可集成的处理单元数量呈指数倍增长，这加大了芯片在生产制造时出现瑕疵的可能性。同时，芯片集成密度的增加，也加大了芯片在运行过程中产生故障的概率。因此，对于包含故障处理单元的大规模的处理器阵列，必须使用有效的容错技术对其进行重构，以确保芯片系统的可靠性和稳定性。
　　目前，针对处理器阵列的重构研究主要包含两个方向：一是尽可能地增大重构后目标阵列的规模大小，从而提高无故障处理单元的使用率；二是尽可能的减少目标阵列中各处理单元之间的互连长度，从而降低整个芯片的通信花费、能耗以及时延等，以提高系统的性能。
　　针对第一个研究方向，到目前为止，已有专家提出了相关的重构算法，但这些算法大多采用分治的策略，并不能保证所求得的目标阵列是最大的，即全局最优的。通过分析二维处理器阵列的结构特点，本文利用整数规划的思想，在行、列重路由约束下，提出了一个重构最大规模目标阵列的有效算法。该算法首先将阵列中的无故障可用单元描述为整数规划问题中的变量，并把处理器网状结构的约束指定为这些变量的等式或不等式，从而将求解最大规模目标阵列的问题转化为最大化这些变量的和的整数规划问题，而后使用相应的整数规划求解器对其进行求解。实验表明，与现有的算法相比，本文所提出的算法能有效地增大目标阵列的规模，从而提高了处理器系统的可靠性。
　　针对第二个研究方向，在重构得到的目标阵列中，已有专家提出了相关的优化算法来减少该目标阵列中各处理单元之间的互连长度（即长链接数目），但这些算法均不能同时实现最大规模目标阵列和最少长链接数目这两个目标。为了重构得到一个高性能的目标阵列，使其不仅具有最大的规模，而且包含最少的长链接数目，本文在行、列重路由约束下提出了一种基于网络流的阵列重构算法。该算法通过为待重构的处理器阵列构建相应的网络流模型，将求解包含最少长链接数目且规模最大的目标阵列问题转化为最小花费最大流问题，并使用相应的网络流算法对其进行求解。实验表明，与现有的算法相比，本文所提出的算法能有效地减少目标阵列中的长链接数目，从而提升了系统的性能。

目录

声明

第一章 绪论

§1.1 研究背景

§1.2 国内外研究现状和存在的问题

§1.3 研究目标及主要贡献

§1.4 论文主要组织结构

第二章 基本定义

§2.1 体系结构

§2.2 线性规划的基础知识

§2.3 网络流的基础知识

第三章 相关问题描述及算法回顾

§3.1 相关问题描述

§3.2 相关算法回顾

§3.3 本章小结

第四章 基于整数规划的最大目标阵列重构算法

§4.1 动机

§4.2 算法描述

§4.3 实验与分析

§4.4 本章小结

第五章 基于网络流的高性能目标阵列重构算法

§5.1 动机

§5.2 算法描述

§5.3 实验与分析

§5.4 本章小结

第六章 总结与展望

§6.1 内容总结

§6.2 未来工作展望

参考文献

研究生期间发表论文及参加科研情况说明

致谢