A GRASP Algorithm for Multi-objective Circuit Partitioning

Circuit partitioning plays a crucial role in very large-scale integrated circuit (VLSI) physical design automation. With current trends, partitioning with multiple objectives which includes cutsize, area, delay, and power obtains much concentration. In this paper, a multi-objective greedy randomized adaptive search procedure (GRASP) is presented for simultaneous cutsize and circuit delay minimization. Each objective is assigned a preference or weight to direct the search procedure and generate a variety of efficient solutions by changing the preference. To get a good initial partition with minimal cutsize and circuit delay, the gain of each module in a circuit is computed by considering both signal nets and circuit delay. The performance of the proposed algorithm is evaluated on a standard set of partitioning benchmark. The experimental results show that the proposed algorithm can generate a set of Pareto optimal solutions and is efficient for tackling multi-objective circuit partitioning.

Partition of a Travel into Circuits

In this paper, a sufficient condition to partition a travel into circuits of length at least 3 is provided， In particular, a necessary and sufficient condition to partition a planar travel into such circuits, which can he verified in polynomial time, is provided，

一种基于多级聚类的VLSI电路划分算法

超大规模集成电路(VLSI)划分问题,属于NP-难问题。结合了贪心随机自适应搜索过程(GRASP)和多级聚类方法的思想,提出了一种基于多级聚类的电路划分算法。算法采用贪心随机自适应的思想改进了多级划分方法中重边粗化聚类(HEM)方法。通过对ISPD98的18个标准测试样例的测试结果表明,该方法与著名的划分工具h Metis相比,划分质量有一定的提高,最多可以改进3%左右。

A hybrid multi-objective PSO algorithm with local search strategy for VLSI partitioning

Very large scale integration （VLSI） circuit par- titioning is an important problem in design automation of VLSI chips and multichip systems; it is an NP-hard combi- national optimization problem. In this paper, an effective hy- brid multi-objective partitioning algorithm, based on discrete particle swarm optimzation （DPSO） with local search strat- egy, called MDPSO-LS, is presented to solve the VLSI two- way partitioning with simultaneous cutsize and circuit delay minimization. Inspired by the physics of genetic algorithm, uniform crossover and random two-point exchange operators are designed to avoid the case of generating infeasible so- lutions. Furthermore, the phenotype sharing function of the objective space is applied to circuit partitioning to obtain a better approximation of a true Pareto front, and the theorem of Markov chains is used to prove global convergence. To improve the ability of local exploration, Fiduccia-Matteyses （FM） strategy is also applied to further improve the cutsize of each particle, and a local search strategy for improving circuit delay objective is also designed. Experiments on IS- CAS89 benchmark circuits show that the proposed algorithm is efficient.

Automatic architecture design for distributed quantum computing

In distributed quantum computing(DQC),quantum hardware design mainly focuses on providing as many as possible high-quality inter-chip connections.Meanwhile,quantum software tries its best to reduce the required number of remote quantum gates between chips.However,this“hardware first,software follows”methodology may not fully exploit the potential of DQC.Inspired by classical software-hardware co-design,this paper explores the design space of application-specific DQC architectures.More specifically,we propose Auto Arch,an automated quantum chip network(QCN)structure design tool.With qubits grouping followed by a customized QCN design,AutoArch can generate a near-optimal DQC architecture suitable for target quantum algorithms.Experimental results show that the DQC architecture generated by Auto Arch can outperform other general QCN architectures when executing target quantum algorithms.