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

Heuristic Search with Cut Point Based Strategy for Critical Node Problem

Journal of computer Science & Technology 2024年第6期39卷 1328-1340页

作者： Zhi-Han Chen Shao-Wei Cai Jian Gao Shi-Ke Ge Chan-Juan Liu Jin-Kun Lin School of Computer Science and Technology University of Chinese Academy of SciencesBeijing 101408China Key Laboratory of System Software(Chinese Academy of Sciences)and State Key Laboratory of Computer Science Institute of SoftwareChinese Academy of SciencesBeijing 100190China College of Information Science and Technology Northeast Normal UniversityChangchun 130024China School of Computer Science and Technology Dalian University of TechnologyDalian 116024China SeedMath Technology Limited Beijing 100086China

The critical node problem(CNP)aims to deal with critical node identification in a graph,which has extensive applications in many *** CNP is a challenging task due to its computational complexity,and it attracts much attention from both academia and *** this paper,we propose a population-based heuristic search algorithm called CPHS(Cut Point Based Heuristic Search)to solve CNP,which integrates two main *** first one is a cut point based greedy strategy in the local search,and the second one involves the functions used to update the solution pool of the ***,a mutation strategy is applied to solutions with probability based on the overall average similarity to maintain the diversity of the solution *** are performed on a synthetic benchmark,a real-world benchmark,and a large-scale network benchmark to evaluate our *** with state-of-the-art algorithms,our algorithm has better performance in terms of both solution quality and run time on all the three benchmarks.

关键词： local search cut point heuristic search critical node problem

来源：评论

学校读者我要写书评

暂无评论

I/O lower bounds for auto-tuning of convolutions in CNNs 21

I/O lower bounds for auto-tuning of convolutions in CNNs

引用

26th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2021

作者： Zhang, Xiaoyang Xiao, Junmin Tan, Guangming State Key Laboratory of Computer Architecture Institute of Computing Technology Chinese Academy of Sciences University of Chinese Academy of Science China

ISBN: (纸本)9781450382946

Convolution is the most time-consuming part in the computation of convolutional neural networks (CNNs), which have achieved great successes in numerous practical applications. Due to the complex data dependency and the increase in the amount of model samples, the convolution suffers from high overhead on data movement (i.e., memory access). This work provides comprehensive analysis and methodologies to minimize the communication for the convolution in CNNs. With an in-depth analysis of the recent I/O complexity theory under the red-blue game model, we develop a general I/O lower bound theory for a composite algorithm which consists of several different sub-computations. Based on the proposed theory, we establish the data movement lower bound results for two main convolution algorithms in CNNs, namely the direct convolution and Winograd algorithm, which represents the direct and indirect implementations of a convolution respectively. Next, derived from I/O lower bound results, we design the near I/O-optimal dataflow strategies for the two main convolution algorithms by fully exploiting the data reuse. Furthermore, in order to push the envelope of performance of the near I/O-optimal dataflow strategies further, an aggressive design of auto-tuning based on I/O lower bounds, is proposed to search an optimal parameter configuration for the direct convolution and Winograd algorithm on GPU, such as the number of threads and the size of shared memory used in each thread block. Finally, experiment evaluation results on the direct convolution and Winograd algorithm show that our dataflow strategies with the auto-tuning approach can achieve about 3.32× performance speedup on average over cuDNN. In addition, compared with TVM, which represents the state-of-the-art technique for auto-tuning, not only our auto-tuning method based on I/O lower bounds can find the optimal parameter configuration faster, but also our solution has higher performance than the optimal solution provided

关键词： Convolution

来源：评论

学校读者我要写书评

暂无评论

Accelerate Bit Manipulation in XiangShan Processer Using RISC-V B Extension and Instruction Fusion

Accelerate Bit Manipulation in XiangShan Processer Using RIS...

引用

2022 International Conference on Cloud Computing, Internet of Things, and computer Applications, CICA 2022

作者： Zhang, Fawang Tang, Dan Cai, Ye College of Computer Science and Software Engineering Shenzhen University Shenzhen China State Key Laboratory of Computer Architecture Institute of Computing Technology Beijing China

ISBN: (纸本)9781510656673

In the field of high-performance computing, some application scenarios make extensive use of bit manipulation. RISC-V foundation issues B extension to reduce the number of instructions during the static compilation. But this extension does not cover the more frequent operations fully. Instruction fusion technology can fuse multiple instructions into one instruction at the decode stage to dynamically reduce the number of instructions. Therefore, this technology can supplement RISC-V B extension uncovered instruction, enhancing the processor’s capabilities for bit manipulation. This paper implements the RISC-V B extension 1.0 version on the Xiangshan processor. For accelerating more bit manipulation, we profiled general benchmarks by the simulator, proposed ten new instructions fusion targets, and implemented a fusion decode unit. Finally, we use Coremark and SPEC CPU 2006 integer to evaluate the performance. The Coremark results show that dynamic instructions reduce by 18.14%, and the performance improves by 12.09%. © 2022 SPIE.

关键词： Decoding

来源：评论

学校读者我要写书评

暂无评论

A low overhead on-chip path delay measurement circuit

A low overhead on-chip path delay measurement circuit

引用

18th Asian Test Symposium, ATS 2009

作者： Pei, Songwei Li, Huawei Li, Xiaowei Key Laboratory of Computer System and Architecture Institute of Computing Technology Chinese Academy of Sciences China Academy of Sciences Graduate University of Chinese Beijing 100190 China

ISBN: (纸本)9780769538648

In this paper, we present a novel on-chip path delay measurement circuit for efficiently detecting and debugging of delay faults in the fabricated integrated circuits. Several delay stages are employed in the proposed circuit, whose delay ranges are increased by a factor of two gradually from the last to the first delay stage. Thus, the proposed method can achieve a large delay measurement range with a small quantity of delay stages. Experimental results show that a significant reduction in both delay measurement time and area overhead can be obtained compared to the previous Vernier Delay Line based delay measurement schemes. In addition, by conducting delay compensation, the proposed method can achieve both improved delay measurement resolution and measurement accuracy. © 2009 IEEE.

关键词： Timing circuits

来源：评论

学校读者我要写书评

暂无评论

A low-complexity synchronization based cache coherence solution for many cores

A low-complexity synchronization based cache coherence solut...

引用

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

作者： Lin, Wei Fan, DongRui Huang, He Yuan, Nan Ye, Xiaochun Key Laboratory of Computer System and Architecture Institute of Computing Technology Chinese Academy of Sciences Beijing China Graduate University of Chinese Academy of Sciences Beijing China

ISBN: (纸本)9780769538365

computer architectures make a dramatic turn away from improving single-processor performance towards improved parallel performance through integrating many cores in one chip. However, providing directory based coherence protocols for these platforms is too complex and expensive. As a substitute, we propose a synchronization based cache coherence solution, which uses different cache policies according to three flexible software guided scopes (exclusion, producer and consumer scopes) to solve the data-race and coherence problem. Furthermore, this protocol implements word dirty bits (only one bit per word is needed in each L1 cache line) and a special hardware synchronization manager (HSM) to support multi-writer, the write-validate policy and to eliminate the remote un-cache spinning at the "flag". We evaluate Godson-T, a platform supporting this protocol, against an idealized interleaved dual tag directory based protocol on the Splash2 and two bioinformatics benchmarks. The performance of the synch-based protocol is degraded only at 3.2% on average, but the real chip area is reduced at 32% even if the overhead of HSM is included. © 2009 IEEE.

关键词： Synchronization

来源：评论

学校读者我要写书评

暂无评论

Multi-tiered on-demand resource scheduling for VM-based data center 09

Multi-tiered on-demand resource scheduling for VM-based data...

引用

2009 9th IEEE/ACM International Symposium on Cluster Computing and the Grid, CCGRID 2009

作者： Song, Ying Wang, Hui Yaqiong, Li Feng, Binquan Sun, Yuzhong Key Laboratory of Computer System and Architecture Institute of Computing Technology Chinese Academy of Sciences Beijing China Graduate University Chinese Academy of Sciences Beijing China

ISBN: (纸本)9780769536224

The trend of using virtualization for server consolidation is more and more popular in enterprise data center. However, ondemand resource allocation among the concurrent hosted services in such a virtualized environment is still a challenge. In order to optimize resource allocation among services in data center, this paper proposes a multi-tiered resource scheduling scheme which automatically provides on-demand capacities to the hosted services via resources flowing among VMs. We model the resource flowing using optimization theory. Based on this model, we present a global resource flowing algorithm in the multi-tiered resource scheduling scheme. This algorithm preferentially ensures performance of some critical services by degrading of others to some extent when resource competition arises. Using our RAINBOW prototype, we evaluate the multitiered resource scheduling scheme with the performance improvements for the most critical services up to 9%˜16%, which are 75% of the maximum improvement margin, while performance degradation of others is up to 2%, and leads to 1%˜5% improvements in resource utilization than RAINBOW without resource flowing. Compared with the existent scheme, our work leads to 9% less improvements for critical services, while introduces 39% less degradation to low priority services. © 2009 IEEE.

关键词： Resource allocation

来源：评论

学校读者我要写书评

暂无评论

Address remapping for static NUCA in noc-based degradable chip-multiprocessors

Address remapping for static NUCA in noc-based degradable ch...

引用

16th IEEE Pacific Rim International Symposium on Dependable Computing, PRDC 2010

作者： Wang, Ying Zhang, Lei Han, Yinhe Li, Huawei Li, Xiaowei Key Laboratory of Computer System and Architecture Institute of Computing Technology Chinese Academy of Sciences Beijing China Graduate University of Chinese Academy of Sciences Beijing China

ISBN: (纸本)9780769542898

Large scale Chip-Multiprocessors (CMPs) generally employ Network-on-Chip (NoC) to connect the last level cache (LLC), which is generally organized as distributed NUCA (non-uniform cache access) arrays for scalability and efficiency. On the other hand, aggressive technology scaling induces severe reliability problems, causing on-chip components (e.g., cores, cache banks, routers) failure due to manufacture defects or on-line hardware faults. Typical degradable CMPs should possess the ability to work around defects by disabling faulty components. For static NUCA architecture, when cache banks attached to a computing node are disabled, however, certain physical address sections will no longer be accessible. Prior approaches such as sets reduction introduced in Intel Xeon processor 7100 series enable turning off cache banks by masking certain sets bits in physical address1, which greatly wastes cache capacity. In this paper, we propose to tackle the above problem in a finer granularity to restrict the capacity loss in NUCA cache. Cache accesses to isolated nodes are redirected based on the utility-driven address remapping scheme that reduces data blocks conflicts in fault-tolerant shared-LLC. We evaluate our technique using GEMS simulator. Experimental results show that address remapping achieves significant improvement over the conventional cache sizing scheme. © 2010 IEEE.

关键词： Network-on-chip

来源：评论

学校读者我要写书评

暂无评论

Robust test generation for power supply noise induced path delay faults

Robust test generation for power supply noise induced path d...

引用

2008 Asia and South Pacific Design Automation Conference, ASP-DAC

作者： Fu, Xiang Li, Huawei Hu, Yu Li, Xiaowei Key Laboratory of Computer System and Architecture Institute of Computing Technology Chinese Academy of Sciences Beijing China Graduate School Chinese Academy of Sciences Beijing China

ISBN: (纸本)9781424419227

In deep sub-micron designs, the delay caused by power supply noise (PSN) can no longer be ignored. A PSN-induced path delay fault (PSNPDF) model is proposed in this paper, and should be tested to enhance chip quality. Based on precise timing analysis, we also propose a robust test generation technique for PSNPDF. Concept of timing window is introduced into the PSNPDF model. If two devices in the same feed region simultaneously switch in the same direction, the current waveform of the two devices will have an overlap and excessive PSN will be produced. Experimental results on ISCAS'89 circuits showed test generation can be finished in a few seconds. ©2008 IEEE.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Mapping of pipeline flow chart onto mesh-based multi-core NoC architecture

Mapping of pipeline flow chart onto mesh-based multi-core No...

引用

2010 10th IEEE International Conference on Solid-state and Integrated Circuit Technology

作者： Yang, Haofan Xiao, Ruijin Liu, Liang Jing, Ming-E Yu, Zhiyi Zeng, Xiaoyang Zhou, Dian State Key Laboratory of ASIC and System Fudan University Shanghai 200433 China School of Computer Science Fudan University China

ISBN: (纸本)9781424457984

Among current outstanding research problems in NoC Design, mapping application onto NoC is one of the core issues to be explored. In this paper, we propose two methods for mapping a pip elined flow chart onto mesh-based NoC system: Communication Length Concerned (CLC) method and Space Restricted (SR) method after a simple pre-process. The former significantly reduces the latency and energy consumption in inter-core communication while latter method provides a trade-off for run-time mapping based on the former one. Results show that, compared with normal mapping, the CLC method reduces about 43.3% and 28.6% in communication latency and energy consumption, respectively;while the SR method reduces about 37.6% communication latency and 24% energy consumption. The two methods discussed in this paper could be used as guidance for mapping pipeline flow charts on homogenous mesh-based NoC architectures. ©2010 IEEE.

关键词： Mapping

来源：评论

学校读者我要写书评

暂无评论

M-IVC: Using multiple input vectors to minimize aging-induced delay

M-IVC: Using multiple input vectors to minimize aging-induce...

引用

18th Asian Test Symposium, ATS 2009

作者： Jin, Song Han, Yinhe Zhang, Lei Li, Huawei Li, Xiaowei Yan, Guihai Key Laboratory of Computer System and Architecture Institute of Computing Technology Chinese Academy of Sciences Beijing China Chinese Academy of Sciences Graduate University Beijing China

ISBN: (纸本)9780769538648

Negative bias temperature instability (NBTI) has been a significant reliability concern in current digital circuit design due to its effect of increasing the path delay with time and in turn degrading the circuit performance. NBTI degradation has strong dependence on input pattern and duty cycles. Based on this observation, we propose to apply multiple input vectors to the combination circuit in a non-uniform way during standby mode. Multiple input vectors can enhance the capability to control the circuit nodes, achieve smaller duty cycles to reduce the stress time of gates and thus mitigate static NBTI. A constrained multi-object optimization model is formalized to find the optimal combination of duty cycles for timing-critical paths, which in turn minimizes the increase of path delay. An ATPG-like procedure is then presented to generate the corresponding input vectors. Experimental results demonstrate that the delay increase of timing-critical paths can be mitigated significantly under long time NBTI effect (10-year) by only applying a small number of vectors. © 2009 IEEE.

关键词： Negative bias temperature instability

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：