Search

Search Results

• DESCRIPTION OF GRAPHS WITH ASSOCIATIVE OPERATIONS IN SET@L PROGRAMMING LANGUAGE

  I. I. Levin , I. V. Pisarenko, D. V. Mikhailov , A. I. Dordopulo

  2020-10-11

  Abstract ▼

  Usually, an information graph with associative operations has a sequential (“head/tail”) or
  parallel (“half-splitting”) topology with invariable quantity of operational vertices. If computational
  resource is insufficient for the implementation of all vertices, the reduction transformations
  of graphs with basic topologies do not allow for the creation of an efficient resource-independent
  program. In fact, the “half-splitting” variant is characterized by irregular connections between
  iterations, and the “head/tail” structure has an increased data duty cycle in the reduced form.
  In this paper, we propose to transform the topology of a graph with associative operations into a
  combined variant with sequential and parallel fragments of calculations. The resultant combined
  topology depends on computational resource of a parallel computer system, and such transformation
  provides the improvement of specific performance for the reduced computing structure.
  The considered topology contains isomorphic subgraphs with the “half-splitting” topology, which
  include the maximal number of hardwarily implemented operational vertices, but the processing of
  intermediate data is performed using the “head/tail” principle. The computing structure for the
  combined topology has minimal latency and includes one basic subgraph and one vertex with
  feedback. This vertex is obtained as a result of the “head/tail” block reduction. We develop an
  algorithm for the conversion of the initial sequential graph to various combined topologies or to
  the limiting case of the “half-splitting” topology with regard to available hardware resource.
  Within traditional methods of parallel programming, it is possible to describe the variety of topologies
  only as a set of separated subprograms. To create an efficient resource-independent program,
  we propose the application of the Set@l programming language. We describe the
  “head/tail” and “half-splitting” principles as the attributes of set processing methods in Set@l.
  Resource-independent program uses these types and parallelism attributes for the modification of
  topology and further reduction of performance in the corresponding aspects.

• ANALYSIS OF ADVANCED COMPUTER TECHNOLOGIES FOR CALCULATION OF EXACT APPROXIMATIONS OF STATISTICS PROBABILITY DISTRIBUTIONS

  А.К. Melnikov, I.I. Levin, А.I. Dordopulo, I.V. Pisarenko

  6-19

  2021-10-05

  Abstract ▼

  In the paper we consider the solution of a computationally expensive problem such as calcu-lation of statistics probability distribution with the help of modern computer technologies. To re-duce computational complexity and to provide a sufficient level of criteria efficiency not less than the specified threshold, we suggest to use Δ-exact approximations. To calculate exact approxima-tions, we use the method of second order, based on solution of a system of linear equations. Owing to this method, it is possible to calculate exact approximations for the maximum values of sample parameters for available computational resource. The most laborious part of the method of second order is the procedure of sequential detection of the vectors of possible solutions and test if the vectors belong to the set of solutions. The system solution set membership test for the vectors of possible solutions is data independent, so the algorithm can be data-parallelized. We give the al-gorithm complexity equation for calculation of exact approximations of statistics probability dis-tributions. Using this equation, we calculated the complexity of modern practical problems for the samples with the parameters (N, n) of the alphabet power and the sample size: (256,1280), (128,640), (128, 320), and (192,3200) for the accuracy of calculations =10-5. The computational complexity is 9.68·1022-1.60·1052 operations, and its average value is about 4.55·1025 operations, the number of tested vectors is 6.50·1023-1.39·1050, and the number of solutions is 4.67·1012-5.60·1025, respectively. The total solution time for clock-round duration of calculations cannot exceed 30 days or 2.592·106 sec. For the obtained complexity evaluation, we analysed abilities of modern cluster computer systems based on general-purpose processors, graphic accelerators, and FPGA-based reconfigurable computer systems. For each technology, we determined the number of computational nodes needed for calculation of exact approximations with the specified parameters during the specified time. We proved that it is impossible to obtain a solution for the required pa-rameters of exact approximations of statistics probability with the help of the reviewed modern computer technologies. In conclusion, we claim that it is necessary to analyse the abilities of ad-vanced computer technologies based of quantum and photonic computers, and also hybrid com-puter systems for calculation of exact approximations of statistics probability distributions with the specified parameters during reasonable time

• ANALYSIS OF ADVANCED COMPUTER TECHNOLOGIES FOR CALCULATION OF EXACT APPROXIMATIONS OF STATISTICS PROBABILITY DISTRIBUTIONS

  А.К. Melnikov, I.I. Levin, А.I. Dordopulo, L.M. Slasten

  2022-11-01

  Abstract ▼

  The paper is devoted to the evaluation of the hardware resource of computer systems for
  solving a computational-expensive problem such as calculation of the probability distributions of
  statistics by the second multiplicity method based on Δ-exact approximations for samples with a
  size of 320-1280 characters and an alphabet power of 128-256 characters, and with an accuracy
  of Δ=10-5. The total solution time should not exceed 30 days or 2.592·106 seconds for 24/7 computing.
  Owing to the use of the properties of the second multiplicity method, the computational complexity
  of the calculations can be brought to the range of 9.68·1022-1.60·1052 operations with the
  number of tested vectors of 6.50·1023-1.39·1050. The solution of this problem for the specified parameters
  of samples during the given time requires the hardware resource which cannot be provided
  by modern computer means such as processors, graphics accelerators, programmable logic
  integrated circuits. Therefore, in the paper we analyze the possibilities of promising quantum and
  photon technologies for solving the problem with the given parameters. The main advantage of
  quantum computer systems is the high speed of calculations for all possible parameter values.
  However, quantum acceleration will not be achieved to calculate the probability distributions of
  statistics due to the need to check all the obtained solutions. Here, the number of obtained solutions
  corresponds to the dimension of the problem. In addition, due to the current development
  level of the quantum hardware components, it is impossible to create and use the 120-qubit quantum
  computers for the solution of the considered problem. Photon computers can provide high
  computation speed at low power consumption and require the smallest number of nodes to solve
  the considered problem. However, unsolved problems with the physical implementation of efficient
  memory elements and the lack of available hardware components make the use of photon computer
  technologies impossible for calculation of the probability distributions of statistics in the near
  future (5-7 years). Therefore, it is most reasonable to use hybrid computer systems containing
  nodes of different architectures. To solve the problem on various hardware platforms (generalpurpose
  processors, GPUs, FPGAs) and configurations of hybrid computer systems, we suggest to
  use an architecture independent high-level programming language SET@L. The language combines
  the representation of calculations as sets and collections (based on the alternative set theory
  of P. Vopenka), the absolutely parallel form of the problem represented as an information graph,
  and the paradigm of aspect-oriented programming.

• HIGH-LEVEL TOOLS FOR TRANSLATION OF C-APPLICATIONS INTO APPLICATIONS IN DATAFLOW LANGUAGE COLAMO

  A.I. Dordopulo, A.A. Gulenok, A.V. Bovkun, I.I. Levin, V.A. Gudkov, S.A. Dudko

  2021-02-25

  Abstract ▼

  In the paper we review software tools for translation of sequential C-programs into scalable
  parallel-pipeline programs written in the COLAMO language, used for programming of reconfigurable
  computer systems. In contrast to existing tools of high-level synthesis, the translation result
  is not an IP-core of a task fragment, but a complex task solution for multichip reconfigurable
  computer systems with automatic synchronization of data and control signals. We analysed the
  main translation steps of a sequential C-program such as transformation into an information
  graph, analysis of data dependencies and selection of functional subgraphs, transformation into a
  scalable resource-independent parallel-pipeline form, and scaling a COLAMO-program for a
  specified multichip reconfigurable computer system. A program is scaled with the help of performance
  reduction methods, applied to a completely parallel form of a task (an information graph),
  adapted to the architecture of a reconfigurable computer system. We developed several rules,significantly reducing the number of transformation steps of task scaling, and providing a continuous flow of data processing in the functional subgraphs of the task. The developed software tools
  for translation of C-programs into FPGA configuration files significantly decrease the synthesis
  time of a task computing structure for multichip RCSs and the total task solution time.