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

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Comparison resonant magnetoelectric effects in positive magnetostrictive/piezoelectric and negative magnetostrictive/piezoelectric laminate composites

引用

Journal of Computational and Theoretical Nanoscience 2016年第9期13卷 5672-5675页

作者： Chen, Lei Key Lab. of Computer Vision and Intelligent Information System Chongqing University of Arts and Sciences Chongqing402160 China

Magnetoelectric (ME) effect is investigated in various bilayer composites with various magnetostrictive materials FeCuNbSiB, FeSiB, Ni, FeNi and Terfenol-D. Compared with the ME composites, FeSiB/PZT Ni/PZT, Terfenol-D/PZT, FeNi/PZT and FeCuNbSiB/PZT, the resonant ME voltage coefficient of FeCuNbSiB/PZT composite reaches 12.5 V/Oe and is larger than that of other four bilayer ME composites. This feature enables the FeCuNbSiB/PZT composite to possess more highly efficient magneto-electric energy conversion ability. In additional, the ME voltage coefficient of Ni/PZT exhibits significant hysteresis phenomenon as a function of the dc magnetic field at resonant frequency. The zero-biased ME response is observed and can be attributed to the large intrinsic anisotropic field with obvious hysteresis and remnant magnetization in Ni plate. This result offers the potential applications for highly sensitive magnetic field detection without bias by utilizing bilayer Ni/PZT composite due to its self-biased, self-powered, and ultra-sensitive properties. Copyright © 2016 American Scientific Publishers All rights reserved.

关键词： Magnetostrictive devices

来源：评论

学校读者我要写书评

暂无评论

McRT-STM: A high performance software transactional memory system for a multi-core runtime

McRT-STM: A high performance software transactional memory s...

引用

2006 ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP'06

作者： Saha, Bratin Adl-Tabatabai, Ali-Reza Hudson, Richard L. Chi, Cao Minh Hertzberg, Benjamin Programming System Lab. Microprocessor Technology Lab. Intel Corporation Computer Architecture Lab. Stanford University Palo Alto CA

ISBN: (纸本)1595931899

Applications need to become more concurrent to take advantage of the increased computational power provided by chip level multiprocessing. Programmers have traditionally managed this concurrency using locks (mutex based synchronization). Unfortunately, lock based synchronization often leads to deadlocks, makes fine-grained synchronization difficult, hinders composition of atomic primitives, and provides no support for error recovery. Transactions avoid many of these problems, and therefore, promise to ease concurrent programming. We describe a software transactional memory (STM) system that is part of McRT, an experimental Multi-Core RunTime. The McRT-STM implementation uses a number of novel algorithms, and supports advanced features such as nested transactions with partial aborts, conditional signaling within a transaction, and object based conflict detection for C/C++ applications. The McRT-STM exports interfaces that can be used from C/C++ programs directly or as a target for compilers translating higher level linguistic constructs. We present a detailed performance analysis of various STM design tradeoffs such as pessimistic versus optimistic concurrency, undo logging versus write buffering, and cache line based versus object based conflict detection. We also show a MCAS implementation that works on arbitrary values, coexists with the STM, and can be used as a more efficient form of transactional memory. To provide a baseline we compare the performance of the STM with that of fine-grained and coarse-grained locking using a number of concurrent data structures on a 16-processor SMP system. We also show our STM performance on a non-synthetic workload - the Linux sendmail application. Copyright © 2006 ACM.

关键词： Data storage equipment

来源：评论

学校读者我要写书评

暂无评论

A fast linear-space sequence alignment algorithm with dynamic parallelization framework

A fast linear-space sequence alignment algorithm with dynami...

引用

IEEE 9th International Conference on computer and Information Technology, CIT 2009

作者： Xiaochun, Ye Dongrui, Fan Wei, Lin Key Lab of Computer System and Architecture Institute of Computing Technology Chinese Academy of Sciences Beijing China

ISBN: (纸本)9780769538365

Exact pairwise sequence alignment algorithms using dynamic programming require quadratic space and time, and this makes these algorithms impractical for large-scale sequences. In this paper, we propose and evaluate a new Anti-Diagonal based Parallel Linear-Space Algorithm (AD-PLSA). It records similarity matrix scores and start points on special anti-diagonals instead of special rows or columns. This algorithm is able to further reduce the total amount of re-computation. It also produces balanced sub-problems with approximately even size, and this is of great benefit to the parallelization. In addition, we establish a dynamic parallelization framework for the efficient acceleration on a symmetric multiprocessor (SMP) platform. The experimental results present liner speedup for long real DNA sequences. Compared with the typical row-col algorithm, our method is able to save more than 30% of the re-computation, and run twice as fast in the backward phase. © 2009 IEEE.

关键词： DNA sequences

来源：评论

学校读者我要写书评

暂无评论

Optimizing sparse matrix vector multiplication using cache blocking method on Fermi GPU

Optimizing sparse matrix vector multiplication using cache b...

引用

13th ACIS International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing, SNPD 2012

作者： Xu, Weizhi Zhang, Hao Jiao, Shuai Wang, Da Song, Fenglong Liu, Zhiyong Key Lab. of Computer System and Architecture Institute of Computing Technology Chinese Academy of Sciences Beijing China Graduate University Chinese Academy of Sciences Beijing China

ISBN: (纸本)9780769547619

It is an important task to tune performance for sparse matrix vector multiplication (SpMV), but it is also a difficult task because of its irregularity. In this paper, we propose a cache blocking method to improve the performance of SpMV on the emerging GPU architecture. The sparse matrix is partitioned into many sub-blocks, which are stored in CSR format. With the blocking method, the corresponding part of vector x can be reused in the GPU cache, so the time spent on accessing the global memory for vector x is reduced heavily. Experimental results on GeForce GTX 480 show that SpMV kernel with the cache blocking method is 5x faster than the unblocked CSR kernel in the best case. © 2012 IEEE.

关键词： Graphics processing unit

来源：评论

学校读者我要写书评

暂无评论

A computer-supported collab.rative learning platform based on clouds

引用

Journal of Computational Information systems 2011年第11期7卷 3811-3818页

作者： Li, Jiandun Peng, Junjie Zhang, Wu Han, Fangfang Yuan, Qin Joint Lab of Cloud Computing School of Computer Engineering and Science Shanghai University Shanghai 200072 China Key Laboratory of Computer System and Architecture Institute of Computing Technology Chinese Academy of Sciences Beijing 100190 China

computer-supported collab.rative learning (CSCL) is an emerging branch of learning science concerned with studying how people can learn together with the help of computers. As an indispensable ingredient, computer mediation evolves through couples of phases, e.g. centralized server, peer-to-peer network, grid computing. Nevertheless, with daily rising trend on requirement's dynamic changes in service, existing models fall short to respond on demand. Thus, in this paper, by taking advantage of cloud computing, we propose a feasible CSCL platform and the experiments show that it can not only fulfill the basic requirement of CSCL, but also respond to learner's dynamic need on demand. Copyright © 2011 Binary Information Press.

关键词： Peer to peer networks

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

A facial expression model for human-like agent

A facial expression model for human-like agent

引用

2006 IEEE Conference on Robotics, Automation and Mechatronics

作者： Bin, Yang Peifa, Jia State Key Lab. of Intelligent Technology and System Department of Computer Science Tsinghua University Beijing China

ISBN: (纸本)1424400244

A major unsolved problem in human-like agent is the construction and application of realistic human facial expression models. Human-like agents should interact with human by recognizing human facial expression and synthesizing facial expressions to show their emotional states. However there is no a uniform model for both recognition and synthesis of facial expression. In this paper, we present a model for solving this challenging task. First, we setup a muscle-based facial model and use muscles' contraction as controlling factors because all the facial actions are driven by the muscles. An orthogonal facial expression space is constructed by regarding each controlling factor as a dimension. Then muscles' contractions are calculated from facial images to construct the facial vector. Thus the facial vector can be used on the facial expression synthesis system of human-like agent. In this paper, we also present a facial function to describe the dynamic procedure of facial expressions. Last, this paper points out the direction of future work. © 2006 IEEE.

关键词： Anthropomorphic robots

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：