检索结果-内蒙古大学图书馆

Synthesizing Invariants for Polynomial Programs by Semidefinite Programming

ACM Transactions on Programming Languages and Systems 2025年第1期47卷 1-35页

作者： Wu, Hao Wang, Qiuye Xue, Bai Zhan, Naijun Zhi, Lihong Yang, Zhi-Hong State Key Lab. of Computer Sciences Institute of Software Chinese Academy of Sciences Beijing China University of Chinese Academy of Sciences Beijing China Fermat Labs Huawei Inc. Dongguan China Key Lab. of System Software and State Key Lab. of Computer Science Institute of Software Chinese Academy of Sciences Beijing China Key Laboratory of High Confidence Software Technology School of Computer Science Peking University Beijing China School of Mathematics and Statistics Central South University Changsha China

Constraint-solving-based program invariant synthesis takes a parametric invariant template and encodes the (inductive) invariant conditions into constraints. The problem of characterizing the set of all valid parameter assignments is referred to as the strong invariant synthesis problem, while the problem of finding a concrete valid parameter assignment is called the weak invariant synthesis problem. For both problems, the challenge lies in solving or reducing the encoded constraints, which are generally non-convex and lack efficient solvers. In this article, we propose two novel algorithms for synthesizing invariants of polynomial programs using semidefinite programming (SDP): (1) The Cluster algorithm targets the strong invariant synthesis problem for polynomial invariant templates. Leveraging robust optimization techniques, it solves a series of SDP relaxations and yields a sequence of increasingly precise under-approximations of the set of valid parameter assignments. We prove the algorithm’s soundness, convergence, and weak completeness under a specific robustness assumption on templates. Moreover, the outputs can simplify the weak invariant synthesis problem. (2) The Mask algorithm addresses the weak invariant synthesis problem in scenarios where the aforementioned robustness assumption does not hold, rendering the Cluster algorithm ineffective. It identifies a specific subclass of invariant templates, termed masked templates, involving parameterized polynomial equalities and known inequalities. By applying variable substitution, the algorithm transforms constraints into an equivalent form amenable to SDP relaxations. Both algorithms have been implemented and demonstrated superior performance compared to state-of-the-art methods in our empirical evaluation. © 2025 Copyright held by the owner/author(s).

关键词： Polynomial approximation

来源：评论

学校读者我要写书评

暂无评论

POSTER: STAR (Space-Time Adaptive and Reductive) Algorithms for Real-World Space-Time Optimality

引用

ACM SIGPLAN Notices 2017年第8期52卷 455-456页

作者： Tang, Yuan You, Ronghui School of Computer Science School of Software Fudan University Shanghai Key Lab. of Intelligent Information Processing State Key Lab. of Computer Architecture Institute of Computing Technology Chinese Academy of Sciences China

It's important to hit a space-time balance for a real-world algorithm to achieve high performance on modern shared-memory multi-core or many-core systems. However, a large class of dynamic programs with more than $O(1)$ dependency achieve optimality either in space or time, but not both. In the literature, the problem is known as the fundamental space-time tradeoff. By exploiting properly on the runtime system, we show that our STAR (Space-Time Adaptive and Reductive) technique can help these dynamic programs to achieve sublinear parallel time bounds while still maintaining work-, space-, and cache-optimality in a processor- and cache-oblivious fashion. © 2017 ACM.

关键词： Real time systems

来源：评论

学校读者我要写书评

暂无评论

Prevention from Soft Errors via architecture Elasticity

引用

Journal of computer Science & Technology 2014年第2期29卷 247-254页

作者：尹一笑陈云霁郭崎陈天石 State Key Lab of Computer Architecture and Microprocessor Research Center Institute of Computing Technology Chinese Academy of Sciences University of Chinese Academy of Sciences Loongson Technology Corporation Limited IBM Research-China

Due to the decreasing threshold voltages, shrinking feature size, as well as the exponential growth of on-chip transistors, modern processors are increasingly vulnerable to soft errors. However, traditional mechanisms of soft error mitigation take actions to deal with soft errors only after they have been detected. Instead of the passive responses, this paper proposes a novel mechanism which proactively prevents from the occurrence of soft errors via architecture elasticity. In the light of a predictive model, we adapt the processor architectures h01istically and dynamically. The predictive model provides the ability to quickly and accurately predict the simulation target across different program execution phases on any architecture configurations by leveraging an artificial neural network model. Experimental results on SPEC CPU 2000 benchmarks show that our method inherently reduces the soft error rate by 33.2% and improves the energy efficiency by 18.3% as compared with the static configuration processor.

关键词： soft error energy efficiency architecture elasticity

来源：评论

学校读者我要写书评

暂无评论

Modeling and analyzing method for CPS software architecture energy consumption

Journal of Software

引用

Journal of Software 2013年第11期8卷 2974-2981页

作者： Zhang, Guangquan Zhang, Kan Zhu, Xueyang Chen, Mingcai Xu, Chengkai Shao, Yuzhen School of Computer Science and Technology Soochow University Suzhou China State Key Lab. for Novel Software Technology Nanjing University Nanjing China State Key Lab. of Computer Science Institute of Software Chinese Academy of Science Beijing China

CPS is a kind of networked embedded system. Its trustworthiness and cost are impacted by energy consumption. So design a low-power, high trustworthiness CPS has been a major challenge. Modeling and analyzing the energy consumption of CPS software architecture at design stage can help to find the energy consumption design defects. These methods can effectively improve the trustworthiness of the CPS software and reduce development costs. Against this problem, first introduce the concept of the energy consumption time Petri nets;then through analyzing the characteristics of the CPS software energy consumption, use energy consumption time Petri nets to construct the CPS software architecture energy consumption model and discuss the energy consumption problems of CPS software such as lowest energy consumption, largest energy consumption and average energy consumption;Finally, indicate the effectiveness of the proposed method by an instance. © 2013 ACADEMY PUBLISHER.

关键词： Energy utilization

来源：评论

学校读者我要写书评

暂无评论

A fault-tolerant System-on-Programmable-Chip based on Domain-Partition and blind reconfiguration

A fault-tolerant System-on-Programmable-Chip based on Domain...

引用

2010 NASA/ESA Conference on Adaptive Hardware and Systems, AHS 2010

作者： Shang, Lihong Zhou, Mi Hu, Yu School of Computer Science and Engineering Beihang University China Key Lab. of Computer System and Architecture ICT Chinese Academy of Sciences China

ISBN: (纸本)9781424458875

Field programmable gate arrays (FPGAs) are widely used in building Systems-on-Programmable-Chips (SOPCs) since they contain plenty of reconfigurable heterogeneous resources providing the facility to implement various intellectual property cores. However, with the shrinking device feature size and the increasing die area, nowadays FPGAs can be deeply affected by the errors induced by electromigration and radiation, which results in challenges of building reliable SOPCs. In this paper, a SOPC implementing a smart 1553B bus node is presented to investigate the challenges and illustrate a feasible approach for building a complex system aimed at high reliability and low recovery latency on a commercial FPGA. First, a general reliability model, the Domain-Partition (DP) model, is introduced to formulate the SOPCs which contain multiple alternative configurations proving the fault recovery capability. The assignment of the alternative configurations for maximizing the reliability is then determined according to a first-order optimal solution under the DP framework. Finally, the blind reconfiguration technique is used to reduce the recovery latency. The experiments based on a Monte Carlo simulation approach are carried out to evaluate the reliability and the latency. The obtained results show that higher reliability is attainable with less overhead than the generic triple-modular redundancy method. © 2010 IEEE.

关键词： Monte Carlo methods

来源：评论

学校读者我要写书评

暂无评论

Improving the network energy efficiency in MapReduce systems

Improving the network energy efficiency in MapReduce systems

引用

2013 IEEE 2013 22nd International Conference on computer Communication and Networks, ICCCN 2013

作者： Wang, Lin Zhang, Fa Liu, Zhiyong Institute of Computing Technology Chinese Academy of Sciences Beijing China University of Chinese Academy of Sciences Beijing China Chinese State Key Lab. for Computer Architecture ICT CAS Beijing China

ISBN: (纸本)9781467357746

Apart from servers, the energy consumed by enormous amount of network devices in data centers also emerges as a big problem. Existing work on energy- efficient data center networking primarily focuses on traffic engineering to consolidate flows and shut down unused devices, not considering another important factor, virtual machine assignment, which has been shown to have a big influence on traffic engineering. Moreover, the lack of information about upper layer applications leads to misunderstand the traffic patterns of the network. This may result in poor effectiveness in the traffic-based optimization in practice. In this paper, we aim to achieve better network energy efficiency in MapReduce systems by combining virtual machine assignment and traffic engineering. By exploiting the characteristics of MapReduce applications, we provide a unified model to describe this problem. Due to its NP-hardness, a general framework is proposed to solve it, where virtual machines are first clustered and then different virtual machine assignments are generated greedily and a local search procedure is used to improve them. The local search procedure depends on the results of an energy-efficient routing provided by GEERA. GEERA is an approximate algorithm designed to select routing paths for flows. Experimental results confirm the efficiency of GEERA, as well as the overall framework. By using this framework, up to 20% more energy savings can be achieved compared with sole traffic engineering solutions. © 2013 IEEE.

关键词： MapReduce

来源：评论

学校读者我要写书评

暂无评论

Energy-efficient network routing with discrete cost functions

Energy-efficient network routing with discrete cost function...

引用

9th Annual Conference on Theory and Applications of Models of Computation, TAMC 2012

作者： Wang, Lin Fernández Anta, Antonio Zhang, Fa Hou, Chenying Liu, Zhiyong Key Lab. of Intelligent Information Processing Institute of Computing Technology Chinese Academy of Sciences China Institute IMDEA Networks Spain China State Key Lab. for Computer Architecture Institute of Computing Technology Chinese Academy of Sciences China Graduate University of Chinese Academy of Sciences China

ISBN: (纸本)9783642299513

Energy consumption is an important issue in the design and use of networks. In this paper, we explore energy savings in networks via a rate adaptation model. This model can be represented by a cost-minimization network routing problem with discrete cost functions. We formulate this problem as an integer program, which is proved to be NP-hard. Then a constant approximation algorithm is developed. In our proposed method, we first transform the program into a continuous-cost network routing problem, and then we approximate the optimal solution by a two-step rounding process. We show by analysis that, for uniform demands, our method provides a constant approximation for the uniform network routing problem with discrete costs. A bicriteria network routing problem is also developed so that a trade-off can be made between energy consumption and network delay. Analytical results for this latter model are also presented. © 2012 Springer-Verlag.

关键词： Network routing

来源：评论

学校读者我要写书评

暂无评论

Safe Exit Controllers Synthesis for Continuous-time Stochastic Systems 63

Safe Exit Controllers Synthesis for Continuous-time Stochast...

引用

63rd IEEE Conference on Decision and Control, CDC 2024

作者： Xue, Bai State Key Lab. of Computer Science Beijing China University of Chinese Academy of Sciences Beijing China

ISBN: (纸本)9798350316339

This paper tackles the problem of generating safe exit controllers for continuous-time systems described by stochastic differential equations (SDEs). The primary aim is to develop controllers that maximize the lower bounds of the exit probability that the system escapes from a safe but uncomfortable set within a specified time frame and guide it towards a comfortable set. The paper considers two distinct cases: one in which the boundary of the safe set is a subset of the boundary of the uncomfortable set, and the other where the boundaries of the two sets do not intersect. To begin, we present a sufficient condition for establishing lower bounds on the exit probability in the first case. This condition serves as a guideline for constructing a point-wise optimization using linear programs. The linear programming problem is designed to implicitly synthesize an optimal exit controller online that maximizes the lower bounds of the exit probability. The method employed in the first case is then extended to the second one. Finally, we demonstrate the effectiveness of the proposed approaches on one example. © 2024 IEEE.

关键词： Continuous time systems

来源：评论

学校读者我要写书评

暂无评论

Memory Access Complexity Analysis of SpMV in RAM (h) Model

Memory Access Complexity Analysis of SpMV in RAM (h) Model

引用

10th IEEE International Conference on High Performance Computing and Communications

作者： Yuan E Zhang Yun-quan Sun Xiangzheng Lab. of Parallel Computing ISCAS 100190 China Graduate University of Chinese Academy of Sciences 100190 China State Key Lab. of Computer Science CAS 100190 China

ISBN: (纸本)9780769533520

Sparse Matrix-Vector Multiplication is an important computational kernel in scientific applications, and CSR storage algorithm often performs poorly on modern computer systems. But the register-level blocking algorithm can optimize memory hierarchy access, reduce memory access time, and then improve the performance. RAM (h) is a computation model that has h-level memory hierarchies. It indicates that different implementation forms of the same algorithm can have different memory access complexity. In this paper, we try to analyze memory access compelxity of two implementation forms of SpMV(which are CSR storage algorithm and register-level blocking algorithm) and to predict the performance of SpMV through combining the memory access complexity analysis and the data movement/floating point operation ratio analysis. The performance data of two forms and Statistical results of miss number of L1, L2 and TLB on Pentium IV platform are listed. Model analytical results matched well with experimental results.

关键词： SpMV sparse matrix-vector multiplication RAM (h) model memory access complexity

来源：评论

学校读者我要写书评

暂无评论

A reconfigurable routing method for fault-tolerant mesh-based network on chip

引用

Journal of Information and Computational Science 2013年第1期10卷 157-165页

作者： Liu, Yanhua Ruan, Ying Lai, Zongsheng Sun, Ling Institute of Microelectronics Circuit and System East China Normal University Shanghai 200241 China Jiangsu Provincial Key Lab. of ASIC Design Nantong University Nantong 226019 China State Key Laboratory of Computer Architecture Institute of Computing Technology Chinese Academy of Sciences Beijing 100190 China

As the semiconductor industry advances to nano-technology points, Network on Chip (NoC) components are becoming vulnerable to errors during the system operation. Consequently, fault-tolerant techniques for NoC are needed to achieve high reliability. In this paper, we present a fault-tolerant routing method to tolerate faulty routers in a two-dimension (2D) mesh-based NoC. With this method, the system can have a multi-router fault-tolerant capability and the routing path can be dynamically reconfigured to support different situations caused by faulty routers in NoC. Fault-tolerance capability and system performance of the proposed method are evaluated through analysis and simulations. Theoretical analysis and simulation results show that the proposed method can enhance the reliability of system and offer considerable fault-tolerance capability. © 2013 by Binary Information Press.

关键词： Network-on-chip

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：