Search

Search Results

• STUDY OF POSSIBILITIES OF USING PHOTONIC AND QUANTUM COMPUTING TECHNOLOGIES TO CALCULATE EXACT PROBABILITY DISTRIBUTIONS OF STATISTIC VALUES FROM FINITE DISCRETE SEQUENCES

  А.К. Melnikov

  121-136

  2025-12-30

  Abstract ▼

  This article explores the feasibility of using photonic and quantum computing technologies to calculate exact probability distributions of discrete sequence statistics, assuming the existence of working hardware prototypes of computing systems and the development of the required quantum algorithms. The performance evaluation of computing systems based on photonic computing technologies is based on materials from the Sarov Scientific Center for Physics and Microphysics of the Russian Academy of Sciences. The performance of a quantum computing system is assessed by comparing the time it takes to solve a boson sampling problem from a given distribution on a computing system with known performance and the time it takes to solve it on a quantum computing system. To assess the feasibility of using photonic and quantum computing technologies to calculate exact distributions, modern methods for calculating them are considered. These methods are based on solving the type multiplicity equation and a system of linear equations in non-negative integers. Analytical expressions determining the computational complexity of these methods are presented. The values of the boundaries of the parameters of exact distributions accessible for calculation using photonic and quantum computing technologies are determined. A comparison of the obtained results with the results of using multiprocessor computing technologies to calculate exact distributions using various methods is presented. An analysis of the feasibility of using photonic and quantum computing technologies to calculate exact distributions is conducted by comparing the number of parameter pairs that can be calculated for exact distributions with the total number of distribution parameters within the Fisher region, which determines a fivefold increase in sample size over the alphabet size. An analysis of the data on the number of sample parameters shows that with increasing performance of the computing technologies used, the ability to calculate exact distributions increases. However, even with the most powerful quantum technologies, this number does not exceed one-tenth of the total number of exact distributions required for statistical analysis of discrete sequences in alphabets up to 256 characters long

• 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.

• LIMITING THE NUMBER OF DIFFERENT TEST VECTORS TO OBTAIN ALL SOLUTIONS OF A SYSTEM OF THE SECOND MULTIPLICITY LINEAR EQUATIONS ON MULTIPROCESSOR COMPUTER SYSTEM

  А.К. Melnikov

  2021-07-18

  Abstract ▼

  In the paper we consider calculation of all integer nonnegative solutions of a linear equation
  system (LES) of the second types order by a method of sequential vector testing. The method
  checks whether a vector is a solution of the LES. We consider different vectors and test if they
  belong to the set of the LES solutions. As a result, after such testing we obtain all solutions of the
  LES. The LES testing vector consists of the elements which are the numbers of some alphabet signs
  with the same number of occurrences in the sample. The LES unites the number of occurrences of
  the elements of all types into the considering sample, the power of the alphabet, the size of the
  sample, and the limitation for the maximum number of occurrences of the alphabet signs into the
  sample. The LES solution is the base for calculation of exact statistics probability distributions
  and their exact approximations by the method of the second types order. Here, the exact approximations
  are Δexact distributions. The difference between the Δexact distributions and the exact
  distributions does not exceed the predefined arbitrary small value Δ. The number of test vectors is
  one of those which defines algorithmic complexity of the method of second types order. Without it,
  it is impossible to define the parameters of samples, and to calculate exact distributions and their
  exact approximations for limited hardware resource. We consider various test vectors for the limited
  maximum number of occurrences of the alphabet signs in the sample, and for the unlimited
  one. We have obtained formulas to calculate the number of tests for various vectors. Here, the
  values of the power of the alphabet, the size of the sample, and the limitations for the maximum
  number of occurrences of the alphabet signs into the sample can be arbitrary. Using the obtained
  formulas, we can get all integer nonnegative solutions of the LES of the second types order. We
  can use the obtained formula for analysis of algorithmic complexity of calculations of exact distributions
  and their exact approximations with the predefined accuracy Δ.