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

Network decomposition using kernighan-lin strategy aided harmony search algorithm

SWARM AND EVOLUTIONARY COMPUTATION 2012年 7卷 1-6页

作者： Ezhilarasi, G. A. Swarup, K. S. Indian Inst Technol Dept Elect Engn Madras 600036 Tamil Nadu India

Power system is a large-scale network with a number of components and interconnections for which centralized control becomes cumbersome. For multi-area computations, decentralization is necessary. For implementation of this approach network decomposition becomes an essential task. In this paper the network decomposition problem is solved as an optimization problem using the harmony search (HS) algorithm. To improve the performance of the HS algorithm, a widely used graph bi-partitioning method called kernighan-lin (KL) strategy is used in the improvisation process. KL strategy is used in the partitioning of digital and VLSI circuits and is suitable for bi-partitioning networks. The connectivity of the partitioned clusters are checked by means of graph traversal techniques. Simulation are carried out on IEEE Standard systems and found to be very effective in decomposition of the system hierarchically. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Network decomposition Distributed computing Harmony search algorithm kernighan-lin algorithm

来源：评论

学校读者我要写书评

暂无评论

KL_GA: an application mapping algorithm for mesh-of-tree (MoT) architecture in network-on-chip design

引用

JOURNAL OF SUPERCOMPUTING 2015年第11期71卷 4056-4071页

作者： Fang, Juan Yu, Lu Liu, Sitong Lu, Jiajia Chen, Tan Beijing Univ Technol Coll Comp Sci Beijing 100124 Peoples R China

As the very large-scale integrated circuit designs enter the deep sub-micron era, many-core processors are regarded as promising architectures to keep up with the Moore's law. To provide effective communications between the on-chip components, network-on-chip was proposed as a new paradigm that exhibits better scalability than the traditional buses. There have been previous researches on application mappings to reduce the power consumption, the network latency and the network area overhead. However, some of the previous proposed algorithms such as the kernighan-lin algorithm (KL) and some genetic algorithms (GA) have the problem of finding the local best result instead of a global optimal solution. In this paper, we propose a novel application mapping algorithm for the mesh-of-tree network topology, called KL_GA algorithm. Our proposed algorithm takes the advantage of both the kernighan-lin algorithm and genetic algorithms to reduce the overall communication cost. Our KL_GA algorithm first generates a mapping solution using a KL-based method. In order to avoid the appearance of premature phenomena, we next apply a GA-based algorithm to get rid of the population trapped in the local optimum and re-generate a new population. Our evaluations show that, compared to the random mapping algorithm, our KL_GA algorithm saves the power by 21.6 % and reduces the network latency by 16.3 % on the average.

关键词： NoC kernighan-lin algorithm Genetic algorithm MoT topology

来源：评论

学校读者我要写书评

暂无评论

Direct graph k-partitioning with a kernighan-lin like heuristic

引用

OPERATIONS RESEARCH LETTERS 2006年第6期34卷 621-629页

作者： Traeff, Jesper Larsson NEC Europe Ltd C&C Res Labs D-53757 St Augustin Germany

We show that the Kemighan-lin like linear time heuristic for bipartitioning unweighted graphs by Fiduccia and Mattheyses can be generalized to k-partitioning with the same time bounds, avoiding the logarithmic increase incurred by recursive bipartitioning. Furthermore, the direct heuristic allows a better control of the cut. (c) 2005 Elsevier B.v. All rights reserved.

关键词： graph partitioning k-partitioning bipartitioning kernighan-lin algorithm

来源：评论

学校读者我要写书评

暂无评论

EFFICIENT MULTIPLE-WAY NETWORK-PARTITIONING algorithm

引用

COMPUTER-AIDED DESIGN 1993年第5期25卷 269-280页

作者： KIM, JU LEE, CH KIM, M [a]Department of Electrical Engineering Korea Advanced Institute of Science Technology Cheongryang PO Box 150 Seoul 130–650 Korea

The paper investigates the following multiple-way network-partitioning problem: given a network with sizes for its cells, partition the cells of the network into multiple blocks so as to minimize the number of nets interconnecting cells in different blocks while balancing the blocks' sizes. There is conflict between the two objectives, the minimizing of cutset costs and size balancing. The concepts of balance cost and balance gain are used to represent the degree of size balancing of a partition. A new cost function is proposed which accommodates the inherent conflict by combining the two objectives into a single weighted sum. An iterative improvement algorithm for the network-partitioning problem that uses the cost function is then presented. In comparison with existing algorithms, which are efficient only when the variance in the cell sizes is not too large, the proposed algorithm deals with a large size variance efficiently without any performance degradation. Experimental results for a variety of networks show that the proposed algorithm outperforms the Sanchis algorithm, which is the only existing multiple-way network-partitioning algorithm that the authors have found. The performance gap between the proposed algorithm and the Sanchis algorithm becomes bigger as the variance in cell size and/or the number of blocks to be partitioned increase.

关键词： ELECTRONICS-DESIGN AUTOMATION CIRCUIT PARTITIONING MULTIPLE-WAY NETWORK-PARTITIONING PROBLEMS kernighan-lin algorithm CUTSETS SIZE BALANCES

来源：评论

学校读者我要写书评

暂无评论

On implementation choices for iterative improvement partitioning algorithms

引用

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS 1997年第10期16卷 1199-1205页

作者： Hagen, LW Huang, DJH Kahng, AB Cadence Design Syst Inc San Jose CA 95134 USA AvanWise Inc Fremont CA 94538 USA Univ Calif Los Angeles Dept Comp Sci Los Angeles CA 90095 USA

Iterative improvement partitioning algorithms such as the FM algorithm of Fiduccia and Mattheyses [8], the algorithm of Krishnamurthy [13], and Sanchis's extensions of these algorithms to multiway partitioning [16] all rely on efficient data structures to select the modules to be moved from one partition to the other, The implementation choices for one of these data structures, the gain bucket, is investigated, Surprisingly, selection from gain buckets maintained as last-in-first-out (LIFO) stacks leads to significantly better results than gain buckets maintained randomly (as in previous studies of the FM algorithm [13], [16]) or as first-in-first-out (FIFO) queues. In particular, LIFO buckets result in a 36% improvement over random buckets and a 43% improvement over FIFO buckets for minimum-cut bisection, Eliminating randomization from the bucket selection not only improves the solution quality, but has a greater impact on FM performance than adding the Krishnamurthy gain vector. The LIFO selection scheme also results in improvement over random schemes for multiway partitioning [16] and for more sophisticated partitioning strategies such as the two-phase FM methodology [2], Finally, by combining insights from the LIFO gain buckets with the Krishnamurthy higher-level gain formulation, a new higher-level gain formulation is proposed, This alternative formulation results in a further 22% reduction in the average cut cost when compared directly to the Krishnamurthy formulation for higher-level gains, assuming LIFO organization for the gain buckets.

关键词： Fiduccia-Mattheyses algorithm gain bucket implementation hypergraph partitioning iterative movement kernighan-lin algorithm multiway partitioning VLSI netlist partitioning

来源：评论

学校读者我要写书评

暂无评论

EFFICIENT algorithm FOR GRAPH-PARTITIONING PROBLEM USING A PROBLEM TRANSFORMATION METHOD

引用

COMPUTER-AIDED DESIGN 1989年第10期21卷 611-618页

作者： LEE, CH PARK, CI KIM, M Department of Electrical Engineering Korea Advanced Institute of Science and Technology PO Box 150 Cheongryang Seoul 130-650 South Korea

This paper shows that the uniform k- way partitioning problem can be transformed into the max-cut problem using a graph modification technique. An iterative algorith, based on kernighan-lin's (KL) method, for partitioning graphs is presented that exploits the problem equivalence property. The algorithm deals with nodes of various sizes without any performance degradation. The computing time per pass of the algorithm is O(itkN 2 ), where N is the number of nodes in the given graph. In practice, only a small number of passes are typically needed, leading to a fast approximation algorithm for k- way partitioning. Experimental results show that the proposed algorithm outperforms the KL algorithm in the quality of solutions. The performance gap between the proposed and KL algorithms becomes much bigger as the amount of size differences between nodes increases.

关键词： electronic design automation circuit partitioning k- way graph-partitioning problem kernighan-lin algorithm maximum cutset

来源：评论

学校读者我要写书评

暂无评论

Hardware Implementation of LU Decomposition Using Dataflow Architecture on FPGA

Hardware Implementation of LU Decomposition Using Dataflow A...

引用

5th International Conference on Computer Science and Information Technology (CSIT)

作者： Eljammaly, Mahmoud Hanafy, Yasser Wahdan, Abdelmoniem Bayoumi, Amr Arab Acad Sci & Technol & Maritime Transport Cairo Egypt

ISBN: (纸本)9781467358255

Recent FPGA technology advances permitted the hardware implementation of selected software functions to enhance programs performance. Most of the work done was only concerned with integer operations. Little effort addressed floating point operations. In this paper we propose a dataflow implementation of the LU decomposition on FPGA.A modified kernighan-lin based task partitioning and assignment algorithm is presented in this paper. The algorithm showed acceptable improvement over existing techniques.

关键词： LU factorization tagged-token dataflow architecture FPGA kernighan-lin algorithm parallel processing

来源：评论

学校读者我要写书评

暂无评论

Clustering Optimization Based on Simulated Annealing algorithm for Reconfigurable Systems-On-Chip

Clustering Optimization Based on Simulated Annealing Algorit...

引用

IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering (ElConRus)

作者： Gavrilov, Sergey Zheleznikov, Daniil Khvatov, Vasiliy Chochaev, Rustam Natl Res Univ Elect Technol MIET Russian Acad Sci IPPM RAS Inst Design Problems Microelect Dept CAD Moscow Zelenograd Russia

ISBN: (纸本)9781538643402

A bottom-up circuit clustering step is one of the most significant steps in the reconfigurable systems-on-chip design flow. Qualitative clustering provides the efficiency of subsequent placement and routing steps. The goals of circuit clustering are following: a) achieving the high density by minimizing the number of clusters;b) decreasing time delays by localizing time-critical connections within a cluster and using fast local routing resources. There are several popular solutions to these issues such as partitioning algorithms, bottom-up clustering and heuristic algorithms. In this paper we present a simulated annealing approach for clustering optimization for the reconfigurable system-on-chip based on the "Almaz-14" FPGA. We analyze and compare our algorithm with three popular approaches: basic clustering;kernighan-lin partitioning algorithm;clustering algorithm using Rent's rule. Experimental results on a set of ISCAS' 85 and ISCAS' 89 benchmarks demonstrate that presented algorithm in cooperation with algorithm using Rent's rule has comparable effectiveness to other clustering algorithms.

关键词： field programmable gate array (FPGA) Reconfigurable Systems-on-Chip clustering Rent's rule interconnect kernighan-lin algorithm Simulated Annealing

来源：评论

学校读者我要写书评

暂无评论

An Evaluation Power Model for TriBA Based Application Mapping and Memory-on-Chip 13

An Evaluation Power Model for TriBA Based Application Mappin...

引用

13th International Conference on Natural Computation, Fuzzy Systems and Knowledge Discovery (ICNC-FSKD)

作者： Wang, Xiaojun Shi, Feng Chen, Xu Yin, Fei Beijing Inst Technol Sch Comp Sci & Technol Beijing Peoples R China

ISBN: (纸本)9781538621653

An application mapping algorithm is proposed for using the multicore architecture TriBA. Meanwhile a power consumption evaluating model based topology of on-chip memory network design is presented after application mapping strategy onto various multicore architecture topologies. This paper focuses on evaluating power of on-chip memory and communication network based the approaches of kernighan-lin tri-partitioning algorithm strategy. Utilizing the average hops of links between the components in System-on-Chip, this method computes the average hops which instructions access memory network and communication network on chip. Experimentations with the average hops and established benchmark VOPD show that the proposed method not only can quickly and effectively estimates power consumption but also direct the improvement of Network-on-Chip architecture by using the same application mapping strategy based on topology of multicore architectures.

关键词： Power evaluation Application mapping Memory network on chip kernighan-lin algorithm

来源：评论

学校读者我要写书评

暂无评论

A GRAPH BISECTION algorithm-BASED ON SUBGRAPH MIGRATION

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 1994年第12期E77A卷 2039-2044页

作者： ISOMOTO, K MIMASA, Y WAKABAYASHI, S KOIDE, T YOSHIDA, N HIROSHIMA UNIV FAC ENGN HIGASHIHIROSHIMA 724 JAPAN

The graph bisection problem is to partition a given graph into two subgraphs with equal size with minimizing the cutsize. This problem is NP-hard, and hence several heuristic algorithms have been proposed. Among them, the kernighan-lin algorithm and the Fiduccia-Mattheyses algorithm are well known, and widely used in practical applications. Since those algorithms are iterative improvement algorithms, in which the current solution is iteratively improved by interchanging a pair of two nodes belonging to different subgraphs, or moving one node from one subgraph to the other, those algorithms tend to fall into a local optimum. In this paper, we present a heuristic algorithm based on subgraph migration to avoid falling into a local optimum. In this algorithm, an initial solution is given, and it is improved by moving a subgraph, which is effective to reduce the cutsize. The algorithm repeats this operation until no further improvement can be achieved. Finally, the balance of the bisection is restored by moving nodes to get a final solution. Experimental results show that the proposed algorithm gets better solutions than the kernighan-lin and Fiduccia-Mattheyses algorithms.

关键词： GRAPH PARTITIONING HEURISTIC algorithm kernighan-lin algorithm FIDUCCIA-MATTHEYSES algorithm SUBGRAPH MIGRATION

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：