Home         Authors   Papers   Year of conference   Themes   Organizations        To MES conference

Population VLSI Planning Algorithm by the Method of Crystallization of alternatives field
Authors
	Lebedev B.K.
	Lebedev O.B.
	Lebedeva E.O.
Date of publication
	2020
DOI
	10.31114/2078-7707-2020-4-58-65
Abstract
	An architecture has been developed for a search population algorithm for VLSI planning based on a method of crystallization of alternatives field, based on the structure of a population algorithm that operates with a variety of solutions and implements an evolutionary strategy of random directed search for a solution. The algorithm associated with evolutionary memory seeks to memorize and reuse ways to achieve better results. The team does not have centralized management, and its features are the presence of indirect exchange of information. Indirect exchange is a time-spaced interaction in which one agent changes some areas of co-evolutionary memory, while other agents later use information that has already been changed in these areas. The totality of data on alternatives and their assessments is a scattering of alternatives. In the Crystallization of alternatives field (CAF) method, each solution is formed by a variety of agents. Each agent has many alternative conditions. Each agent may be in one of the alternative states. The decision is determined by a set of alternative states of many agents. The key points of the analysis of alternatives in the process of evolutionary collective adaptation, called by analogy with the processes of isolating objects (crystal formation) crystallization, are considered. An algorithm based on the crystallization of a placer of alternatives has been successfully applied to solve the VLSI planning problem. Such an approach is an effective way to search for rational solutions for optimization problems that can be interpreted as a scattering of alternatives. In the search process, an integral placer of alternatives is formed - the matrix R*. The decision-making process is iterative. Each iteration l includes three steps. At the first stage of each iteration, a constructive algorithm generates nk solutions Pk,. Each solution Pk is represented in the form of a Polish expression formed by sequentially constructing an ordered sequence. Elements of the Polish expression are the identifiers of blocks (of type ri) and section operators (of type H,V). The search for a solution is performed by the set of agents E, by means of the probabilistic choice by each agent eα of the sequence number in the sequence Pk. The solution Pk is transformed into the section tree Dk. Next, convolution of the section tree Dk is carried out. According to the convolution results, the block sizes, the estimate ξk of the solution Pk, and the utility estimate δk of the set of alternatives implemented by the agents in the solution Pk are calculated. A scattering of alternatives Pk is formed. At the second stage, each utility estimate δk of the set of alternatives SRk={ski|i=1,2,…,ne} of each solution Pk formed at the first stage is added to the integral utility estimates of the same sets of alternatives in the original integral placer of alternatives. The paper uses the cyclic method of forming solutions. In this case, the build-up of estimates of the integral utility δij* in the original r*tj of the integral placer of alternatives R* is performed after the complete formation of the set of solutions P at iteration l. At the third stage, the utility estimates δij* of the original integrated placer of alternatives R* are reduced by μ. The proposed planning algorithm allows for better packaging of modules compared to planners of a similar level (packaging quality improved by an average of 3-6%). The temporal complexity of the algorithm obtained experimentally lies in the range of O(n2)-O(n3).
Keywords
	optimization, swarm intelligence, adaptive behavior, method of crystallization of placer alternatives, VLSI, planning.
Library reference
	Lebedev B.K., Lebedev O.B., Lebedeva E.O. Population VLSI Planning Algorithm by the Method of Crystallization of alternatives field // Problems of Perspective Micro- and Nanoelectronic Systems Development - 2020. Issue 4. P. 58-65. doi:10.31114/2078-7707-2020-4-58-65
URL of paper
	http://www.mes-conference.ru/data/year2020/pdf/D068.pdf