Search

Search Results

• METHODOLOGY OF TOPOLOGICAL RESTRICTIONS FOR INTENSIVELY USED FPGA RESOURCE

  К.N. Alekseev, DА. Sorokin, А.L. Leont'ev

  2022-11-01

  Abstract ▼

  In the paper we consider the problem of achieving high real performance of reconfigurable
  computer systems in implementing computationally expensive tasks from various problem areas.
  The parameters of the programs executed on reconfigurable systems determine their real performance.
  The main component of these programs is the computing data processing structures implemented
  as FPGA configuration files. At the same time, one of the key parameters of any computing
  structure is the clock frequency of its operation, which directly affects its performance. However,
  there are several problems concerning the achievement of high clock rates, and they cannot be solved
  with the help of modern CAD tools. The reason is the non-optimal topological placement of functional
  blocks of the computing structure within the field of FPGA primitives, especially with high resource
  utilization. Due to this, the load on the FPGA switching matrix is increasing, and, as a result,
  the connections among functionally dependent FPGA primitives turn out to be much longer than is
  acceptable. In addition, excessive connection length is observed when tracing connections among
  primitives that are placed on different FPGA chips or are physically separated by on-chip peripherals.
  In the paper we describe a methodology which provides optimization of the placement of computing
  structure elements on FPGA primitives, and minimizes the length of traces among primitives,
  and also minimizes the number of traces among physically separated FPGA topological sections.
  To prove the proposed methodology, we implemented the test task "FIR-filter" on a reconfigurable
  computer "Tertius." We have demonstrated the main problems concerning reaching the target clock
  rate and have described a method for their solution. Owing to our methodology, it is possible to
  increase the clock rate; hence, the performance of Tertius will increase by 25% without revising
  the functional circuit of the task’s computing structure. According to our current research of the
  suggested methodology and its efficiency, we claim that CAD tools, used for creating topological
  restrictions and based on our methodology, will significantly reduce the time for developing programs
  with the required characteristics for reconfigurable computer systems.

• SOLUTIONS’ ENCODING IN EVOLUTIONARY METHODS FOR INSTRUMENTAL DESIGN PLATFORM

  E.V. Kuliev, А. А. Lezhebokov, М. М. Semenova, V.A. Semenov

  2020-07-20

  Abstract ▼

  The article considers current issues and analyzes the problems of three-dimensional integration
  and three-dimensional modeling that arise at the design stage during the solution of the
  problem of optimal planning of components of large and extra-large integrated circuits and case
  devices of electronic computing equipment. The main advantages of applying the principles of
  three-dimensional integration are presented and described in sufficient detail, which allow efficiently
  organizing the production of personalized electronics, optimally planning the configuration
  of large and ultra-large integrated circuits, taking into account thermal and energy characteristics.
  In the course of research, the authors developed an approach to encoding decisions based on
  an intelligent mechanism, which is characterized by the presence of built-in means of control of
  acceptable decisions. One of such tools that have experimentally proven their effectiveness is the
  built-in mechanism of “deadly mutations”, which takes into account the status of genes and predetermined
  restrictions on the final configuration of the housing of the designed device. A series of
  general approaches and specific algorithms for solving the planning problem based on the results
  of research by the author's team and modern approaches to solving NP-complete problems are
  proposed. The most important practically significant result of the research of the indicated problem
  is the developed software and instrumental design platform in the modern cross-platform Java
  programming language. The selected development technology allows you to use all the main advantages
  of modern multi-core and multi-processor architectures, to use software multi-threading
  to implement parallel schemes for solving combinatorial problems. The software and tool platform
  has a user-friendly interface, which allows you to effectively manage the process of solving the
  problem of planning the components of large and ultra-large integrated circuits of threedimensional
  integration by visualizing key performance indicators of algorithms on graphs and in
  text statistics blocks. The developed application software made it possible to carry out a series of
  computational experiments based on random data sets, as well as on open-data boron benchmarks
  for such tasks. The results of experimental studies have confirmed the theoretical estimates of the
  time complexity and effectiveness of the proposed approaches and algorithms, including the genetic
  algorithm, which uses the new decision coding mechanism proposed in the work.

• SEARCH POPULATION ALGORITHM FOR VLSI ELEMENTS PLACEMENT

  B.K. Lebedev , O. B. Lebedev , V.B. Lebedev

  2020-11-22

  Abstract ▼

  The paper considers a population search algorithm for the placement of VLSI components.
  By analogy with the process of the emergence and formation of crystals from matter, the process
  of generating a solution by sequential manifestation and concretization of the solution based on an
  integral placer of alternatives is called the method of crystallization of a placer of alternatives.
  The solution Qk of the placement problem is represented as a bijective mapping Fk = A → P, each
  element of the set A corresponds to one single element of the set P and vice versa. The
  metaheuristic of crystallization of a placer of alternatives underlying the algorithm searches for
  solutions taking into account collective evolutionary memory, which means information reflecting
  the history of the search for a solution and the memory of the search procedure. A distinctive feature
  of the metaheuristic used is that it takes into account the tendency to use alternatives from the
  best found solutions. Compact data structures for storing solution interpretations and memory are
  proposed. An algorithm associated with evolutionary memory seeks to memorize and reuse ways
  to achieve better results. The developed algorithm belongs to the class of population. The iterative
  process of finding solutions includes three stages. At the first stage of each iteration, the constructive
  algorithm generates nq solutions Qk. The work of the constructive algorithm is based on the
  indicators of the main integral placer of alternatives – the matrix R, which stores the integral indicators
  of the solutions obtained at the previous iterations. The process of assigning an item to a
  position involves two stages. In the first stage, the element is selected, and in the second stage, the
  position pj. In this case, the restriction must be fulfilled: each element corresponds to one position
  pj. The estimate ξk of the solution Qk and the estimate of the utility δk of the set of positions Pk selected
  by the agents are calculated. The work uses a cyclical method of forming decisions.
  In this case, the accumulation of estimates of the integral utility δk in the main integral placer of
  alternatives R is performed after the complete formation of the set of solutions Q. At the second
  stage of the iteration, the estimates of the integral utility δk are increased in the main integral
  placer of alternatives − the matrix R. At the third stage of the iteration, the estimates of the utility
  δk of the integral placer of alternatives R are reduced by a priori a given value δ*. The algorithm
  ends after the specified number of iterations has been completed. Comparative analysis with other
  solution algorithms was carried out on standard test examples (benchmarks) of the IBM corporation,
  while the solutions synthesized by the CAF algorithm exceed the solution efficiency of the
  known methods by an average of 6%. The time complexity of the algorithm is O(n2)-O(n3)

• DEVELOPMENT OF BIOHEURISTICS FOR CREATING AN INTELLECTUAL SUBSYSTEM FOR MAKING EFFECTIVE DECISIONS OF NP-HARD AND NP-DIFFICULT COMBINATORY-LOGICAL PROBLEMS ON GRAPHS

  D. V. Zaruba , E. V. Kuliev , D.Y. Zaporozhets , M. M. Semenova

  2021-11-14

  Abstract ▼

  The article is devoted to the solution of new topical problems that have arisen in the conditions
  of the modern development of information and nanometer technologies in the field of design,
  as well as the development of new innovative methods that provide effective solutions in polynomial
  time. The article deals with the problem of solving NP-hard problems. The description of the
  procedure for measuring the complexity of the problem is presented the features of NP-hard and
  NP-difficult combinatorial logic problems are described. The main differences between the tasks
  are presented, as well as the problems that one has to face when solving this type of task. The general
  decision-making scheme is presented, consisting of the problem formulation; decisionmaking;
  signal in automatic systems and feedback. At the second stage (formation and selection of
  solutions), the solution is based on a bioinspired algorithm for finding solutions to the traveling
  salesman problem. To solve this problem, a modified bioinspired algorithm based on the behaviorof an ant colony was developed. Unlike other optimization methods, metaheuristic algorithms can
  find global optimal solutions for problems where there are many local solutions due to their random
  nature. These reasons have led to the widespread use of such algorithms in solving various
  optimization problems. Bioinspired algorithms are becoming a new revolution in the field of solving
  optimization problems. The statement of the traveling salesman problem is presented, as well
  as the solution of the problem on the basis of the ant algorithm. Algorithms such as genetic algorithms
  and PSO can be very useful, but they still have some disadvantages in solving multimodal
  optimization problems. These algorithms can find optimal solutions regardless of the physical
  nature of the problem. In the framework of experimental studies, the analysis of the work of
  bioinspired algorithms was carried out: the algorithm of a flock of bats, the bacterial algorithm
  and the ant algorithm.