Efficient Uncertainty Modeling for System Design via Mixed Integer Programming
Efficient Uncertainty Modeling for System Design via Mixed Integer Programming
复制标题
DOI：
10.1109/iccad45719.2019.8942139
复制
发表时间：
2019-07
期刊：
影响因子：
--
通讯作者：
Zichang He;Weilong Cui;Chunfeng Cui;T. Sherwood;Zheng Zhang
中科院分区：
文献类型：
--
作者：
Zichang He;Weilong Cui;Chunfeng Cui;T. Sherwood;Zheng Zhang
后摩尔时代给计算机系统设计的许多方面投下了不确定的阴影。管理这种不确定性需要新的算法工具来进行定量评估。虽然先前的不确定性量化方法，如广义多项式混沌（gPC），展示了如何在物理设备固有的不确定性下精确工作，但这些方法仅关注连续域的变量。然而，随着系统堆栈向上移动到体系结构级别，许多参数被限制为离散（整数）域。本文提出了一种高效、准确的不确定性建模技术——混合广义多项式混沌（M-gPC），用于建筑不确定性分析。M-gPC技术扩展了最初在不确定性量化领域发展起来的广义多项式混沌（gPC）理论，从而可以有效地处理计算机体系结构设计中的混合型（即连续和离散）不确定性。具体来说，我们采用一些随机基函数来捕捉模拟器中不确定参数引起的体系结构级影响。我们还开发了一种新的混合整数规划方法来选择少量的不确定参数样本进行详细的模拟。通过一些高信息量的模拟样本，构建了一个精确的代理模型，以代替用于各种体系结构不确定性分析的循环级模拟器。在芯片多处理器（CMP）模型中，我们能够仅用95个样本估计传播的不确定性，而蒙特卡罗需要5\乘以10^{4}$样本才能达到类似的精度。我们还在一个详细的DRAM子系统上演示了我们的方法的效率和有效性。
The post-Moore era casts a shadow of uncertainty on many aspects of computer system design. Managing that uncertainty requires new algorithmic tools to make quantitative assessments. While prior uncertainty quantification methods, such as generalized polynomial chaos (gPC), show how to work precisely under the uncertainty inherent to physical devices, these approaches focus solely on variables from a continuous domain. However, as one moves up the system stack to the architecture level many parameters are constrained to a discrete (integer) domain. This paper proposes an efficient and accurate uncertainty modeling technique, named mixed generalized polynomial chaos (M-gPC), for architectural uncertainty analysis. The M-gPC technique extends the generalized polynomial chaos (gPC) theory originally developed in the uncertainty quantification community, such that it can efficiently handle the mixed-type (i.e., both continuous and discrete) uncertainties in computer architecture design. Specifically, we employ some stochastic basis functions to capture the architecture-level impact caused by uncertain parameters in a simulator. We also develop a novel mixed-integer programming method to select a small number of uncertain parameter samples for detailed simulations. With a few highly informative simulation samples, an accurate surrogate model is constructed in place of cycle-level simulators for various architectural uncertainty analysis. In the chip-multiprocessor (CMP) model, we are able to estimate the propagated uncertainties with only 95 samples whereas Monte Carlo requires $5\times 10^{4}$ samples to achieve the similar accuracy. We also demonstrate the efficiency and effectiveness of our method on a detailed DRAM subsystem.