All issues

Описаны отличия технологии программирования для параллельных вычислительных систем от технологии последовательного программирования, аргументировано появление новых этапов в технологии: декомпозиция алгоритмов, назначение работ исполнителям, дирижирование и отображение логических исполнителей на физические. Затем кратко рассмотрены вопросы оценки производительности алгоритмов. Обсуждаются вопросы декомпозиции алгоритмов и программ на работы, которые могут бытьвы полнены параллельно.

Difference of software development for parallel computing technology from sequential programming is dicussed. Arguements for introduction of new phases into technology of software engineering are given. These phases are: decomposition of algorithms, assignment of jobs to performers, conducting and mapping of logical to physical performers. Issues of performance evaluation of algorithms are briefly discussed. Decomposition of algorithms and programs into parts that can be executed in parallel is dicussed.

Осуществление передачи сигналов сотовой связи — одна из ключевых задач современного мира. Для улучшения сигнала передаваемой информации необходимо чтобы сигнал не искажался при усилении мощности на базовой станции сотовой связи. Поставленную задачу можно решать самыми различными способами, однако одним из самых простых решений, которое широко используется в индустрии, является добавление нелинейных искажений, позволяющих линеаризовать работу усилителя и устранять интермодуляционные искажения в областях спектра, не используемых для передачи сигнала. В силу большой нагрузки и работы в реальном времени модель, осуществляющая данные искажения, не должна быть громоздкой и иметь большое количество адаптируемых параметров. В данной статье производится анализ современных работ по теме многокритериальной оптимизации и построения моделей для решения задачи предискажения сигнала при помощи данных методов. В статье показывается, что возможно найти структуру (сохранив производительность) и имеющую меньшее количество используемых ресурсов, быстрее, чем полный перебор по всему словарю из заданных параметров.

In this paper, we investigate different alternative ideas for the design of digital predistortion models for radiofrequency power amplifiers. When compared to the greedy search algorithm, these algorithms allow a faster identification of the model parameters combination while still performing reasonably well. For the subsequent implementation, different metrics of model costs and score results in the process of optimization enable us to achieve sparse selections of the model, which balance the model accuracy and model resources (according to the complexity of implementation). The results achieved in the process of simulations show that combinations obtained with explored algorithms show the best performance after a lower number of simulations.

Работа продолжает исследования по способности человека повышать производительность обработки информации, используя параллельную работу или повышение быстродействия анализаторов. Человек получает серию задач, решение которых требует переработки известного количества информации. Регистрируются время и правильность решения. По правильно решенным задачам определяется зависимость среднего времени решения от объема информации в задаче. В соответствии с предложенной ранее методикой задачи содержат вычисления выражений в двух алгебрах, одна из которых ассоциативная, а другая неассоциативная. Для облегчения работы испытуемых в опыте были использованы образные графические изображения элементов алгебры. Неассоциативные вычисления реализовывались в форме игры «Камень, ножницы, бумага». Надо было определить символ-победитель в длинной строке этих рисунков, считая, что они возникают последовательно слева направо и играют с предыдущим символом победителем. Ассоциативные вычисления были основаны на распознавании рисунков из конечного набора простых изображений. Надо было определить, какого рисунка из этого набора в строке не хватает, либо констатировать, что все рисунки присутствуют. В каждой задаче отсутствовало не более одной картинки. Вычисления в ассоциативной алгебре допускают параллельный счет, а при отсутствии ассоциативности возможны только последовательные вычисления. Поэтому анализ времени решения серий задач позволяет выявить последовательную равномерную, последовательную ускоренную и параллельную стратегии вычислений. В экспериментах было установлено, что для решения неассоциативных задач все испытуемые применяли равномерную последовательную стратегию. Для ассоциативных задач все испытуемые использовали параллельные вычисления, а некоторые использовали параллельные вычисления с ускорением по мере роста сложности задачи. Небольшая часть испытуемых при большой сложности, судя по эволюции времени решения, дополняла параллельный счет последовательным этапом вычислений (возможно, для контроля решения). Разработан специальный метод оценки скорости переработки входной информации человеком. Он позволил оценить уровень параллельности расчета в ассоциативных задачах. Была зарегистрирована параллельность уровня от двух до трех. Характерная скорость обработки информации в последовательном случае (примерно полтора символа в секунду) вдвое меньше типичной скорости распознавания изображений человеком. Видимо, разница времени обработки расходуется собственно на процесс вычислений. Для ассоциативной задачи в случае минимального объема информации время решения либо близко к неассоциативному случаю, либо меньше до двух раз. Вероятно, это связано с тем, что для малого числа символов распознавание практически исчерпывает вычисления для использованной неассоциативной задачи.

The work continues research on the ability of a person to improve the productivity of information processing, using parallel work or improving the performance of analyzers. A person receives a series of tasks, the solution of which requires the processing of a certain amount of information. The time and the validity of the decision are recorded. The dependence of the average solution time on the amount of information in the problem is determined by correctly solved problems. In accordance with the proposed method, the problems contain calculations of expressions in two algebras, one of which is associative and the other is nonassociative. To facilitate the work of the subjects in the experiment were used figurative graphic images of elements of algebra. Non-associative calculations were implemented in the form of the game “rock-paper-scissors”. It was necessary to determine the winning symbol in the long line of these figures, considering that they appear sequentially from left to right and play with the previous winner symbol. Associative calculations were based on the recognition of drawings from a finite set of simple images. It was necessary to determine which figure from this set in the line is not enough, or to state that all the pictures are present. In each problem there was no more than one picture. Computation in associative algebra allows the parallel counting, and in the absence of associativity only sequential computations are possible. Therefore, the analysis of the time for solving a series of problems reveals a consistent uniform, sequential accelerated and parallel computing strategy. In the experiments it was found that all subjects used a uniform sequential strategy to solve non-associative problems. For the associative task, all subjects used parallel computing, and some have used parallel computing acceleration of the growth of complexity of the task. A small part of the subjects with a high complexity, judging by the evolution of the solution time, supplemented the parallel account with a sequential stage of calculations (possibly to control the solution). We develop a special method for assessing the rate of processing of input information by a person. It allowed us to estimate the level of parallelism of the calculation in the associative task. Parallelism of level from two to three was registered. The characteristic speed of information processing in the sequential case (about one and a half characters per second) is twice less than the typical speed of human image recognition. Apparently the difference in processing time actually spent on the calculation process. For an associative problem in the case of a minimum amount of information, the solution time is near to the non-associativity case or less than twice. This is probably due to the fact that for a small number of characters recognition almost exhausts the calculations for the used non-associative problem.

В данной работе рассматривается система уравнений магнитной гидродинамики (МГД). Найденные точные решения описывают течения жидкости в пористой среде и связаны с вопросами разработки кернового симулятора и задачами управления параметрами несжимаемой жидкости и направлены на создание отечественной технологии «цифровое месторождение». Центральной проблемой, связанной с использованием вычислительной техники, являются сеточные аппроксимации большой размерности и суперЭВМ высокой производительности с большим числом параллельно работающих микропроцессоров. В качестве возможной альтернативы сеточным аппроксимациям большой размерности разрабатываются кинетические методы решения дифференциальных уравнений и методы «склейки» точных решений на грубых сетках. Сравнительный анализ эффективности вычислительных систем позволяет сделать вывод о необходимости развития организации вычислений, основанных на целочисленной арифметике в сочетании с универсальными приближенными методами. Предложен класс точных решений системы Навье – Стокса, описывающий трехмерные течения для несжимаемой жидкости, а также точные решения нестационарной трехмерной магнитной гидродинамики. Эти решения важны для практических задач управляемой динамики минерализованных флюидов, а также для создания библиотек тестов для верификации приближенных методов. Выделены ряд явлений, связанных с образованием макроскопических структур за счет высокой интенсивности взаимодействия элементов пространственно однородных систем, а также их возникновение за счет линейного пространственного переноса в пространственно-неоднородных системах. Принципиальным является то, что возникновение структур — это следствие разрывности операторов в нормах законов сохранения. Наиболее разработанной и универсальной является теория вычислительных методов для линейных задач. Поэтому с этой точки зрения важными являются процедуры «погружения» нелинейных задач в общие классы линейных за счет изменения исходной размерности описания и расширения функциональных пространств. Отождествление функциональных решений с функциями позволяет вычислять интегральные средние неизвестной, но в то же время ее нелинейные суперпозиции, вообще говоря, не являются слабыми пределами нелинейных суперпозиций приближений метода, т.е. существуют функциональные решения, которые не являются обобщенными в смысле С. Л. Соболева.

In this paper, the system of equations of magnetic hydrodynamics (MHD) is considered. The exact solutions found describe fluid flows in a porous medium and are related to the development of a core simulator and are aimed at creating a domestic technology «digital deposit» and the tasks of controlling the parameters of incompressible fluid. The central problem associated with the use of computer technology is large-dimensional grid approximations and high-performance supercomputers with a large number of parallel microprocessors. Kinetic methods for solving differential equations and methods for «gluing» exact solutions on coarse grids are being developed as possible alternatives to large-dimensional grid approximations. A comparative analysis of the efficiency of computing systems allows us to conclude that it is necessary to develop the organization of calculations based on integer arithmetic in combination with universal approximate methods. A class of exact solutions of the Navier – Stokes system is proposed, describing three-dimensional flows for an incompressible fluid, as well as exact solutions of nonstationary three-dimensional magnetic hydrodynamics. These solutions are important for practical problems of controlled dynamics of mineralized fluids, as well as for creating test libraries for verification of approximate methods. A number of phenomena associated with the formation of macroscopic structures due to the high intensity of interaction of elements of spatially homogeneous systems, as well as their occurrence due to linear spatial transfer in spatially inhomogeneous systems, are highlighted. It is fundamental that the emergence of structures is a consequence of the discontinuity of operators in the norms of conservation laws. The most developed and universal is the theory of computational methods for linear problems. Therefore, from this point of view, the procedures of «immersion» of nonlinear problems into general linear classes by changing the initial dimension of the description and expanding the functional spaces are important. Identification of functional solutions with functions makes it possible to calculate integral averages of an unknown, but at the same time its nonlinear superpositions, generally speaking, are not weak limits of nonlinear superpositions of approximations of the method, i.e. there are functional solutions that are not generalized in the sense of S. L. Sobolev.

Данная работа нацелена на программистов и разработчики, заинтересованных в использовании технологии параллельного программирования для увеличения производительности приложений. Программное обеспечение Oracle Solaris Studio обеспечивает современную оптимизацию и распараллеливание компиляторов для языков C, C ++ и ФОРТРАН, продвинутый отладчик, и оптимизированные математи- ческие и быстродействующие библиотеки. Также включены чрезвычайно мощный инструмент анализа производительности для профилирования последовательных и параллельных приложений, инструмент анализа для обнаружения состязания при передаче данных и блокировки в памяти параллельных программ и IDE. Программное обеспечение Oracle Message Passing Toolkit обеспечивает высокопроизводительные MPI библиотеки и сопряжённую среду во время работы программы, необходимую для приложений передачи сообщений, которые могут работать на одной системе или по всему множеству вычислительных систем с высокопроизводительным сетевым оснащением, включая Gigabit Ethernet, 10 Gigabit Ethernet, InfiniBand и Myrinet. Примеры OpenMP и MPI представлены по всему тексту работы, включая их использование через программные продукты Oracle Solaris Studio и Oracle Message Passing Toolkit для развития и развертывания последовательных и параллельных приложений на основе систем SPARC и x86/x64. В работе продемонстрировано, как развивать и развертывать приложение, распараллеленное с OpenMP и/или MPI.

This paper targets programmers and developers interested in utilizing parallel programming techniques to enhance application performance. The Oracle Solaris Studio software provides state-of-the-art optimizing and parallelizing compilers for C, C++ and Fortran, an advanced debugger, and optimized mathematical and performance libraries. Also included are an extremely powerful performance analysis tool for profiling serial and parallel applications, a thread analysis tool to detect data races and deadlock in memory parallel programs, and an Integrated Development Environment (IDE). The Oracle Message Passing Toolkit software provides the high-performance MPI libraries and associated run-time environment needed for message passing applications that can run on a single system or across multiple compute systems connected with high performance networking, including Gigabit Ethernet, 10 Gigabit Ethernet, InfiniBand and Myrinet. Examples of OpenMP and MPI are provided throughout the paper, including their usage via the Oracle Solaris Studio and Oracle Message Passing Toolkit products for development and deployment of both serial and parallel applications on SPARC and x86/x64 based systems. Throughout this paper it is demonstrated how to develop and deploy an application parallelized with OpenMP and/or MPI.

Предложен метод отображения промежуточных представлений C-, C++-программ в пространство векторов (эмбеддингов) для оценки производительности программ на этапе компиляции, без необходимости исполнения. Использование эмбеддингов для данной цели позволяет не проводить сравнение графов исследуемых программ непосредственно, что вычислительно упрощает задачу сравнения программ. Метод основан на серии трансформаций исходного промежуточного представления (IR), таких как: инструментирование — добавление фиктивных инструкций в оптимизационном проходе компилятора в зависимости от разности смещений в текущей инструкции обращения к памяти относительно предыдущей, преобразование IR в многомерный вектор с помощью технологии IR2Vec с понижением размерности по алгоритму t-SNE (стохастическое вложение соседей с t-распределением). В качестве метрики производительности предлагается доля кэш-промахов 1-го уровня (D1 cache misses). Приводится эвристический критерий отличия программ с большей долей кэш-промахов от программ с меньшей долей по их образам. Также описан разработанный в ходе работы проход компилятора, генерирующий и добавляющий фиктивные инструкции IR согласно используемой модели памяти. Приведено описание разработанного программного комплекса, реализующего предложенный способ оценивания на базе компиляторной инфраструктуры LLVM. Проведен ряд вычислительных экспериментов на синтетических тестах из наборов программ с идентичными потоками управления, но различным порядком обращений к одномерному массиву, показано, что коэффициент корреляции между метрикой производительности и расстоянием до эмбеддинга худшей программы в наборе отрицателен вне зависимости от инициализации t-SNE, что позволяет сделать заключение о достоверности эвристического критерия. Также в статье рассмотрен способ генерации тестов. По результатам экспериментов, вариативность значений метрики производительности на исследуемых множествах предложена как метрика для улучшения генератора тестов.

The method for mapping of intermediate representations (IR) set of C, C++ programs to vector embedding space is considered to create an empirical estimation framework for static performance prediction using LLVM compiler infrastructure. The usage of embeddings makes programs easier to compare due to avoiding Control Flow Graphs (CFG) and Data Flow Graphs (DFG) direct comparison. This method is based on transformation series of the initial IR such as: instrumentation — injection of artificial instructions in an instrumentation compiler’s pass depending on load offset delta in the current instruction compared to the previous one, mapping of instrumented IR into multidimensional vector with IR2Vec and dimension reduction with t-SNE (t-distributed stochastic neighbor embedding) method. The D1 cache miss ratio measured with perf stat tool is considered as performance metric. A heuristic criterion of programs having more or less cache miss ratio is given. This criterion is based on embeddings of programs in 2D-space. The instrumentation compiler’s pass developed in this work is described: how it generates and injects artificial instructions into IR within the used memory model. The software pipeline that implements the performance estimation based on LLVM compiler infrastructure is given. Computational experiments are performed on synthetic tests which are the sets of programs with the same CFGs but with different sequences of offsets used when accessing the one-dimensional array of a given size. The correlation coefficient between performance metric and distance to the worst program’s embedding is measured and proved to be negative regardless of t-SNE initialization. This fact proves the heuristic criterion to be true. The process of such synthetic tests generation is also considered. Moreover, the variety of performance metric in programs set in such a test is proposed as a metric to be improved with exploration of more tests generators.

В данной статье рассматривается проблема централизованного планирования маршрутов передачи данных в сетях, устойчивых к задержкам и разрывам. Исходная проблема расширяется дополнительными требованиями к хранению узлов и процессу связи. Во-первых, предполагается, что связь между узлами графа устанавливается с помощью антенн. Во-вторых, предполагается, что каждый узел имеет хранилище конечной емкости. Существующие работы не рассматривают и не решают задачу с этими ограничениями. Предполагается, что заранее известны информация о сообщениях, подлежащих обработке, информация о конфигурации сети в указанные моменты времени, взятые с определенными периодами, информация о временных задержках для ориентации антенн для передачи данных и ограничения на объем хранения данных на каждом спутнике группировки. Два хорошо известных алгоритма — CGR и Earliest Delivery with All Queues — модифицированы для удовлетворения расширенных требований. Полученные алгоритмы решают задачу поиска оптимального маршрута в сети, устойчивой к разрывам, отдельно для каждого сообщения. Также рассматривается проблема валидации алгоритмов в условиях отсутствия тестовых данных. Предложены и апробированы возможные подходы к валидации, основанные на качественных предположениях, описаны результаты экспериментов. Проведен сравнительный анализ производительности двух алгоритмов решения задачи маршрутизации. Два алгоритма, названные RDTNAS-CG и RDTNAS-AQ, были разработаны на основе алгоритмов CGR и Earliest Delivery with All Queues соответственно. Оригинальные алгоритмы были значительно расширены и была разработана дополненная реализация. Валидационные эксперименты были проведены для проверки минимальных требований «качества» к правильности алгоритмов. Сравнительный анализ производительности двух алгоритмов показал, что алгоритм RDTNAS-AQ на несколько порядков быстрее, чем RDTNAS-CG.

The problem of centralized planning for data transmission routes in delay tolerant networks is considered. The original problem is extended with additional requirements to nodes storage and communication process. First, it is assumed that the connection between the nodes of the graph is established using antennas. Second, it is assumed that each node has a storage of finite capacity. The existing works do not consider these requirements. It is assumed that we have in advance information about messages to be processed, information about the network configuration at specified time points taken with a certain time periods, information on time delays for the orientation of the antennas for data transmission and restrictions on the amount of data storage on each satellite of the grouping. Two wellknown algorithms — CGR and Earliest Delivery with All Queues are improved to satisfy the extended requirements. The obtained algorithms solve the optimal message routing problem separately for each message. The problem of validation of the algorithms under conditions of lack of test data is considered as well. Possible approaches to the validation based on qualitative conjectures are proposed and tested, and experiment results are described. A performance comparison of the two implementations of the problem solving algorithms is made. Two algorithms named RDTNAS-CG and RDTNAS-AQ have been developed based on the CGR and Earliest Delivery with All Queues algorithms, respectively. The original algorithms have been significantly expanded and an augmented implementation has been developed. Validation experiments were carried to check the minimum «quality» requirements for the correctness of the algorithms. Comparative analysis of the performance of the two algorithms showed that the RDTNAS-AQ algorithm is several orders of magnitude faster than RDTNAS-CG.