В статье приведено описание особенностей использования метода взвешенного случайного перебора в задаче поиска субоптимальных разбиений граф-схем параллельных алгоритмов, возникающей при проектировании систем логического управления в базисе логических мультиконтроллеров (ЛМК). Приведен обзор известных методов решения поставленной задачи, большинство из которых являются жадными последовательными методами (за исключением метода случайного перебора) и обеспечивают получение решений неплохого качества в различных областях трехмерного пространства, образованного размерно-стью задачи N и технологическими ограничениями Xmax и Wmax базиса ЛМК за счет наличия зонной зависимости. Комбинируя лучшие стороны жадного и случайного подходов, возможна разработка метода, производящего распределение вершин по блокам разбиения исходя из расчета взвешивающей эвристики с настраиваемой степенью разброса D относительно жадной оценки приращения качества решения. Для указанного метода разработана программная реализация, с использованием которой проведен ряд вычислительных экспериментов. В ходе метаоптимизации выяснено, что оптимальная степень разброса D*=0, что отличается от поведения метода в других задачах дискретной комбинаторной оптимизации и обеспечивает итерационный характер метода только за счет вариации порядка рассмотрения вершин. С указанной степенью разброса для программной реализации метода был реализован вычислительный эксперимент, который показал ее преимущество по качеству результирующих решений по всем показателям качества за исключением интенсивности межблочных взаимодействий. При этом время работы метода в 43 раза больше метода случайного перебора и лимитируется временем оценки качества формируемого разбиения.
The article describes the peculiarities of using weighted random selection method when solving a task of searching for sub-optimal partitions of parallel algorithms flowgraphs-that arises in designing systems of logical control in the basis of logical multicontrollers (LMC). A review of known methods of solving the problem is presented. Most of these methods are ‘greedy’ successive methods (except random selection method) and provide solutions of good quality in various areas of three-dimensional space formed by the dimensionality of problem N and technological limitations Xmax, Wmax of the LMC basis due to the presence of zone dependence. Combining the best aspects of ‘greedy’ and random approaches, it is possible to develop of a method that distributes the vertices in the blocks of the partition based on the weighting heuristics with aт adjustable degree of dispersion D relative to a greedy evaluation of the increment of solution quality. Special software was designed for this method; using this software a series of computational experiments has been carried out. In the course of matho-optimization, it was found that the optimal degree of dispersion D*=zero, which differs from the behaviour of the method in other problems of discrete combinatorial optimization and provides the iterative nature of the method only due to variation of the order of consideration of vertices. A computational experiment was carried out for the software implementation of the method using the indicated degree of dispersion. The experiment showed the advantage in terms of the quality of the output solutions for all quality parameters except for the intensity interblock interactions. At the same time, the working time of the method is 43 times more than that of the method of random selection and is limited by the time of evaluation of the quality of the generated partitioning.
The authors declare that there are no conflicts of interest present.