Інформаційні технології та комп'ютерна інженерія. 2019. № 1
http://ir.lib.vntu.edu.ua//handle/123456789/30259
2024-03-28T14:29:40ZРозпаралелення обчислення канонічного розкладу числа на множники
http://ir.lib.vntu.edu.ua//handle/123456789/30519
Розпаралелення обчислення канонічного розкладу числа на множники
Процько, І. О.; Грищук, О. В.; Prots’ko, I. O.; Gryschuk, O. V.; Процько, И. Е.; Грыщук, А. В.
В статті розглянуто обчислення канонічного розкладу числа на множники з використанням модифікованого методу пробних ділень. Виконання операцій ділення числа розкладу на прості числа для перевірки на кратність вимагає відповідних часових затрат в сучасних комп’ютерних системах. Для їх зменшення використовується бінарне подання числа розкладу в процесі його аналізу на кратність. Для кожного розряду бінарного числа розкладу, що дорівнює одиниці, визначаються залишки його вагового коефіцієнта за модулем відповідного простого числа. Отримані значення залишків акумулюються і потім виконується перевірка накопленого значення на рівність з відповідним значенням з множини простих чисел. У випадку рівності отримуємо елемент кано-нічного розкладу і знову перевіряємо степені цього елемента розкладу на кратність. В протилежному випадку переходимо на наступне більше просте число для подальшої перевірки на кратність, обмежуючись значенням кореня квадратного числа розкладу. Незалежність підзавдань виконання перевірки бінарного подання числа на подільність простими числами дає можливість розпаралелювати виконання розкладу числа в багатоядерних мыкропроцесорах комп’ютерних систем. Серед рівнів паралельності можна послідовно виділити: визначення залишків вагових коефіцієнтів, акумулювання залишків для одиничних розрядів бінарного подання числа розкладу, перевірки на кратність сукупністю простих чисел. Паралельне обчислення розкладу числа досягається виконан-ня алгоритму в багатьох потоках. Програмна реалізація на мові С++, відповідно алгоритму, розподіляє обчислення між потоками, використовуючи пул потоків. В алгоритмі розпаралелення обчислень канонічного розкладу, в залежності від введеного значення числа розкладу, визначається відповідне значення кількості простих чисел та їхніх степенів і рівномірно розподіляється між потоками для виконання аналізу на подільність. В результаті визначено залежність часу обчислення канонічного розкладу числа від кількості потоків в багатоядерних мікропроцесорах лінійки Intel Core i3/i5/i7. Для кожної комп’ютерної системи, що має певну кількість обчислювальних ядер в мікропроцесорах, існує оптимальна кількість потоків, яка забезпечує мінімальний час канонічного розкладу числа на множники.; В статье рассмотрено вычисление канонического разложения числа на множители с использованием модифицировано-го метода пробных делений. Выполнение операций деления числа разложения на простые числа для проверки на кратность требует соответствующих временных потерь в современных компьютерных системах. Для их уменьшения используется бинарное пред-ставление числа разложения в процессе его анализа на кратность. Для каждого разряда бинарного числа разложения, что равняется единице, определяются остатки его весового коэффициента по модулю соответствующего простого числа. Полученные значения остатков аккумулируются и потом выполняется проверка накопленого значения на равенство с соответстующим значением из множества простых чисел. В случае равенства получаем элемент канонического разложения и снова проверяем степени єтого єле-мента розложения на кратность. В противном случае переходим на следующее большее простое число для дальнейшей проверки на кратность, ограничиваясь значеннием квадратного кореня числа разложения. Независимость подзадач выполнения проверки би-нарного представления числа на делимость простыми числами дает возможность распараллеливать выполнение разложения числа в многоядерных микропроцессорах компьютерных систем. Среди уровней параллельности можно последовательно выделить: определение остатков весовых коэффициентов, аккумулирование остатков для единичных разрядов бинарного представления чис-ла разложения, проверки на кратность наборам из простых чисел. Программная реализация на С++, соответственно алгоритму, распределяет вычисления во многих потоках, используя пул потоков. В алгоритме распаралеливания вычислений канонического разложения, в зависимости от введеного значения числа разложения, определяется соответствующее значение количества простых чисел с их степенями и равномерно распределяется между потоками для выполнения анализа на делимость. В результате определе-на зависимость времени вычисления канонического разложения числа от количества потоков в многоядерных микропроцессорах линейки Intel Core i3/i5/i7. Для каждой компьютерной системы, которая имеет определенное количество вычислительных ядер в микропроцессорах, существует оптимальное количество потоков, которое обеспечивает минимальное время канонического разло-жения числа на множители.; The cоmputation of the canonical factorization of a number using the modified trial divisions method has been considered. The performing operations of the division a number of factorization into prime numbers for the testing on a repetition factor demands a respective loss of the execute time in modern computer systems. To reduce them, the presentation of the number of factorization in the binary form is used for the process of analysis on repetition factors. The residuals of weighting coefficient are defined for each digit of the binary represen-tation the number of factorization, which is equal to one. The obtained values of the residuals are accumulated and then the accumulated value is checked for the equality with the corresponding value from the set of prime numbers. In case of equality, we obtain an element of canonical factorization and again check the degrees of this element for a repetition factor. Otherwise, we proceed to the next larger prime number for further checking for a repetition factor. The independence of the subtasks to perform the check of the binary representation of a number on divisibility by prime numbers makes it possible to parallelize the execution of the factorization of a number in multi-core micro-processors of computer systems. Among the levels of the parallelism can be consistently identified: the definition of residual weighting coef-ficients, the accumulation of residuals for bits equel to one of the binary representation of the number of factorization, the checking for a repetition factor from the sets of primes. Software implementation in C++, according to the algorithm, schedules the computations in multi-threads, using a pool of threads. In the algorithm for parallelizing the computations of the canonical factorization, depending on the entered value of the expansion number, the corresponding value of the number of primes with their powers is determined and is evenly distributed between the streams to perform an analysis of divisibility. As a result, the dependence of the run time the computation of the factorization of a number from the number of threads is defined in multi-core processors of Intel Core i3/i5/i7. For the each computer system exist the opti-mal number of the threads, which supports the minimal time of the canonical factorization of a number on the prime numbers.
2019-01-01T00:00:00ZМетод чисельного моделювання гідродинамічних процесів
http://ir.lib.vntu.edu.ua//handle/123456789/30518
Метод чисельного моделювання гідродинамічних процесів
Іванчук, Я. В.; Яровий, А. А.; Коваль, К. О.; Ivanchuk, Y. V.; Yarovyi, А. А.; Koval, К. О.; Иванчук, Я. В.; Яровой, А. А.; Коваль, К. О.
У даній статті наведений чисельний метод моделювання, який застосовується при дослідженні динаміки суцільних в’язких слабостиснених рідин на основі системи рівнянь нерозривності і Нав’є-Стокса. У запропонованому методі використовуєть-ся комплексний підхід використання чисельного розв’язку рівняння нерозривності методом кінцевих об’ємів, а для розв’язку рів-няння Нав’є-Стокса метод розщеплення по фізичним факторам. У статті показано, що метод кінцевих об’ємів, який застосовувався для опису течії як стисненої, так і нестисненої рідин володіє такими важливими перевагами, як наявність хороших консервативних властивостей і допущення дискретизації складних обчислювальних областей в більш прості, чим це дозволяє ізопараметричне кінцево-елементне формулювання задачі або введення узагальнених координат. У метод розщеплення по фізичним факторам вво-диться складова, яка враховує штучну стислевість досліджуваної рідини, що дозволяє спочатку розрахувати проміжкове поле шви-дкостей, яке потім підправляється із врахуванням градієнти тиску. Різницева схема даного методу дозволяє розраховувати поле течії без використання значень вихору і тиску на твердій поверхні. У рамках запропонованого підходу не потрібно розраховувати значення вихору на твердій поверхні. Останнє може бути знайдене по обчисленому полю швидкостей із використанням якого-небудь із різницевих представлень виразу для вихору в граничних точках. Для підтвердження ефективності запропонованого мето-да, в CFD-програмі FlowVision були отримані розв’язки цілого ряду задач зовнішньої гідродинаміки, на прикладі оптікання цилінд-ричної поверхні, які підтвердили стійкість отриманих результатів. Даний метод дозволяє проводити по єдиному алгоритму розра-хунки обтікання плоских, осесиметричних і тривимірних тіл складної конфігурації потоком в’язкої слабостисненої рідини, а також внутрішніх течій в широкому діапазоні чисел Рейнольдса.; В данной статье приведен численный метод моделирования, который применяется при исследовании динамики сплош-ных вязких слабосжатых жидкостей на основе системы уравнений неразрывности и Навье-Стокса. В предложенном методе исполь-зуется комплексный подход использования численного решения уравнения неразрывности методом конечных объемов, а для ре-шения уравнения Навье-Стокса метод расщепления по физическим факторам. В статье показано, что метод конечных объемов, который применялся для описания течения как сжатой, так и несжатой жидкостей обладает такими важными преимуществами, как наличие хороших консервативных свойств и допущения дискретизации сложных вычислительных областей в более простые, чем это позволяет изопараметрическая конечно-элементная формулировка задачи или введение обобщенных координат. В метод рас-щепления по физическим факторам вводится составляющая, которая учитывает искусственную сжимаемость исследуемой жидко-сти, что позволяет сначала рассчитать промежуточное поле скоростей, которое затем подправляется с учетом градиенты давления. Разностная схема данного метода позволяет рассчитывать поле течения без использования значений вихря и давления на твердой поверхности. В рамках предложенного подхода не нужно рассчитывать значение вихря на твердой поверхности. Последнее может быть найдено по вычисленному полю скоростей с использованием какого-либо из разностных представлений выражения для вихря в граничных точках. Для подтверждения эффективности предложенного метода, в CFD-программе FlowVision были получены решения целого ряда задач внешней гидродинамики, на примере оптикания цилиндрической поверхности, которые подтвердили устойчивость полученных результатов. Данный метод позволяет проводить по единому алгоритму расчеты обтекания плоских, осесимметричных и трехмерных тел сложной конфигурации потоком вязкой слабосжатой жидкости, а также внутренних течений в широком диапазоне чисел Рейнольдса.; This article presents a numerical simulation method that is used in the study of the dynamics of continuous viscous weakly com-pressed fluids based on the system of equations of continuity and Navier-Stokes. The proposed method uses a complex approach using the numerical solution of the continuity equation by the finite-volume method, and for solving the Navier-Stokes equation the splitting method by physical factors. The article shows that the finite volume method, which was used to describe the flow of both compressed and uncom-pressed liquids, has such important advantages as the presence of good conservative properties and assumptions of discretization of complex computational domains into simpler ones than isoparametric finite element formulation of the problem or the introduction of generalized coordinates. A component is introduced into the method of splitting according to physical factors, which takes into account the artificial compressibility of the test liquid, which allows you to first calculate the intermediate velocity field, which is then corrected taking into ac-count the pressure gradients. The difference scheme of this method allows one to calculate the flow field without using the values of the vortex and pressure on a solid surface. In the framework of the proposed approach, it is not necessary to calculate the value of the vortex on a solid surface. The latter can be found from the calculated velocity field using any of the difference representations of the expression for the vortex at the boundary points. To confirm the effectiveness of the proposed method, in the FlowVision CFD program, solutions were ob-tained for a number of problems in external hydrodynamics, using the example of a cylindrical surface optics, which confirmed the stability of the results obtained. This method allows one to compute the flow of flat, axisymmetric, and three-dimensional bodies of a complex con-figuration with a flow of a viscous weakly compressed fluid, as well as internal flows in a wide range of Reynolds numbers using a single algorithm.
2019-01-01T00:00:00ZАсоціативні процесори з паралельно-послідовною обробкою даних
http://ir.lib.vntu.edu.ua//handle/123456789/30513
Асоціативні процесори з паралельно-послідовною обробкою даних
Мартинюк, Т. Б.; Денисюк, Н. О.; Круківський, Б. І.; Martyniuk, T. B.; Denysiuk, N. O.; Krukivskyi, B. I.; Мартынюк, Т. Б.; Денисюк, Н. А.; Круковский, Б. И.
Розробка асоціативної пам’яті та паралельних методів асоціативної обробки масивів даних дозволяє подолати обмеження адресного (послідовного) доступу до пам’яті та збільшити швидкодію необчислювальних операцій. Серед методів асоціативної обробки найбільше розповсюдження отримав метод обробки по розрядних зрізах (слайзах), тобто з одночасною обробкою однойменних розрядів усіх слів. В роботі проаналізовано відомі варіанти побудови асоціативних процесорів, базовим вузлом яких є асоціативна пам’ять. Обрано асоціативний процесор з паралельно-послідовним способом обробки елементів числового масиву. Запропоновано дві структури асоціативних процесорів з можливістю виконання операцій пошуку за ключем і пошуку мінімуму/максимуму у числовому масиві. У першому запропонованому варіанті в асоціативному процесорі для пошуку у масиві даних за ключем паралельно-послідовна обробка дозволяє зафіксувати співвідношення n операндів з ключем у вигляді бінарних ознак (=, ≠) в пам’яті результатів на тригерах. У другому запропонованому варіанті в асоціативному процесорі для пошуку екстремальних чисел розширення функціональних можливостей досягається за рахунок роботи в двох режимах: пошук мінімального або максимального числа у масиві n чисел. Особливістю таких процесорів є використання швидкої регістрової пам’яті на лічильниках та паралельної обробки без операції порівняння елементів числового масиву. В цьому випадку можна об’єднати функціональні можливості двох типів запропонованих асоціативних процесорів в одному асоціативному процесорі через подібність їх структурної організації та принципу обробки елементів числового масиву через використання операції декременту у регістровій пам’яті на лічильниках. Розраховано основні параметри запропонованих асоціативних процесорів. Виконано порівняльний аналіз відомих та запропонованих асоціативних процесорів за такими показниками, як апаратна складність та часові витрати. Значною перевагою запропонованих асоціативних процесорів є регулярність структури та менша кількість апаратних витрат. Виграш в апаратних витратах є важливим при реалізації асоціативних процесорів на перспективній елементній базі – ПЛІС.; Разработка ассоциативной памяти и параллельных методов ассоциативной обработки массивов данных позволяет преодолеть ограничения адресного (последовательного) доступа к памяти и увеличить быстродействие невычислительных операций. Среди методов ассоциативной обработки наибольшее распространение получил метод обработки по разрядным срезам (слайзам), то есть с одновременной обработкой одноименных разрядов всех слов. В работе проанализированы известные варианты построения ассоциативных процессоров, базовым узлом которых является ассоциативная память. Выбран ассоциативный процессор с параллельно-последовательным способом обработки элементов числового массива. Предложены две структуры ассоциативных процессоров с возможностью выполнения операций поиска по ключу и поиска минимума / максимума в числовом массиве. В первом предложенном варианте в ассоциативном процессоре для поиска в массиве данных по ключу параллельно-последовательная обработка позволяет зафиксировать соотношение n операндов с ключом в виде бинарных признаков (=, ≠) в памяти результатов на триггерах. Во втором предложенном варианте в ассоциативном процессоре для поиска экстремальных чисел расширение функциональных возможностей достигается за счет работы в двух режимах: поиск минимального или максимального числа в массиве n чисел. Особенностью таких процессоров является использование быстрой регистровой памяти на счетчиках и параллельной обработки без операции сравнения элементов числового массива. В этом случае можно объединить функциональные возможности двух типов предлагаемых ассоциативных процессоров в одном ассоциативном процессоре из-за сходства их структурной организации и принципа обработки элементов числового массива с использованием операции декремента в регистровой памяти на счетчиках. Рассчитаны основные параметры предложенных ассоциативных процессоров. Выполнен сравнительный анализ известных и предложенных ассоциативных процессоров по таким показателям, как аппаратная сложность и временные затраты. Значительным преимуществом предложенных ассоциативных процессоров является регулярность структуры и меньшее количество аппаратных затрат. Выигрыш в аппаратных затратах является важным при реализации ассоциативных процессоров на перспективной элементной базе - ПЛИС.; Development of associative memory and parallel methods of associative processing of numerical arrays allows to overcome the limitations of address (serial) access to memory and increase the speed of non-calculating operations. Among the methods of associative processing the most commonly used methods is processing method by bit cuts (slices), that is the simultaneous processing of the same names of bits of all words. In this paper the known variants of constructing associative processors, the base block of which is associative memory, is analyzed. An associative processor with a parallel-serial method of elements processing of a numerical array is selected. Two structures of associative processors with the ability to perform searches by key and search for a minimum / maximum in a numerical array are proposed. In the first proposed variant of the associative processor for the search by key in the numerical array, parallel-serial processing allows fixing the ratio of n operands with the key in the form of binary attributes (=, ≠) in the memory of the results on the triggers. In the second proposed version of the associative processor for search extreme numbers, the expansion of functionality is achieved by working in two modes: the search for a minimum or maximum number in an array of numbers. The feature of such processors is the using of fast register memory on counters and parallel processing without the operation of comparing elements of a numerical array. In this case, it`s possibly to combine the functionality of the two types of proposed associative processors in one associative processor due to the similarity of their structural organization and the principle of the elements processing of a numerical array using the operation of a decrement in the register memory on the counters. The basic parameters of the proposed associative processors are calculated. A comparative analysis of known and proposed associative processors is performed on indicators such as hardware complexity and time costs. A significant advantage of the proposed associative processor is the regularity of the structure and the smaller amount of hardware costs. The gain in hardware costs is important for the implementing of associative processor on promising element base - FPGA.
2019-01-01T00:00:00ZВисоколінійні буфери й масштабатори напруги на біполярних транзисторах із низьким вхідним струмом
http://ir.lib.vntu.edu.ua//handle/123456789/30512
Високолінійні буфери й масштабатори напруги на біполярних транзисторах із низьким вхідним струмом
Азаров, О. Д.; Медяний, Р. М.; Фігас, А. С.; Azarov, O. D.; Medyaniy, R. M.; Figas, A. S.; Азаров, А. Д.; Медяный, Р. М.; Фигас, А. С.
Буферні пристрої і масштабатори напруги широко застосовуються в різноманітних аналого-цифрових системах, коли потрібно узгодити сигнал у вигляді напруги від малопотужного давача з навантаженням, яке споживає істотно більшу потужність. При цьому буфер напруги характеризується коефіцієнтом передачі напруги близьким до одиниці, а також повинен мати високий вхідний опір і достатну навантажувальну здатність. Масштабатори напруги на відміну від буферів напруги повинені додатково забезпечувати потрібний коефіцієнт передачі підсилення, який може бути істотно більшим за одиницю. Розглянуто схемотехнічні особливості трьох варіантів побудови ядер буферів напруги і масштабаторів напруги. Доведено, що вхідний струм зсуву нуля доці-льно зменшувати шляхом застосуванням у вхідних каскадах підсилювальних n-p-n і p-n-p транзисторів, а також складених транзис-торів Шиклаї. Статичні і динамічні характеристики буферів напруг і масштабаторів напруги повинні відповідати системним вимо-гам пристрою. До статичних характеристик треба віднести у першу чергу похибки передатної характеристики масштабу, зсуву нуля та лінійності. Динаміка цих пристроїв визначається АЧХ та перехідною характеристикою. Проаналізовано статичні і динаміч-ні характеристики шляхом комп'ютерного моделювання де показано, що похибки масштабу буферів напруг і масштабаторів напру-ги не перевищують значень 10 мкВ у діапазоні відповідного сигналу ±5 В, а похибки лінійності 300 нВ. Отримано перехідну харак-теристику яка свідчить, що швидкість наростання вихідної напруги буде не гірше 2000 В/мкс. Здійснено порівняння метрологічних характеристик буферів напруги і масштабаторів напруги у вигляді сукупності ядер і вихідних двотактних підсилювачів постійного струму. Доведено, що застосування цих підсилювачів дозволяє істотно (на 3-4 порядки) покращити навантажувальну здатність схем при збереженні рівня вхідного струму зсуву нуля, а також похибок масштабу і лінійності.; Буферные устройства и масштабаторы напряжения широко применяются в различных аналого-цифровых системах, когда нужно согласовать сигнал в виде напряжения от маломощного датчика с нагрузкой, потребляет существенно большую мощ-ность. При этом буфер напряжения характеризуется коэффициентом передачи напряжения близким к единице, а также должен иметь высокое входное сопротивление и достаточную нагрузочную способность. Масштабатором напряжения в отличие от буфе-ров напряжения должен дополнительно обеспечивать нужный коэффициент передачи усиления, который может быть существенно больше единицы. Рассмотрены схемотехнические особенности трех вариантов построения ядер буферов напряжения и масштаба-тором напряжения. Доказано, что входной ток смещения нуля целесообразно уменьшать путем применением во входных каскадах усилительных n-p-n и p-n-p транзисторов, а также составленных транзисторов Шиклаи. Статические и динамические характеристи-ки буферов напряжений и масштабатором напряжения должны соответствовать системным требованиям устройства. К статических характеристик следует отнести в первую очередь погрешности передаточной характеристики масштаба, смещения нуля и линейно-сти. Динамика этих устройств определяется АЧХ и переходной характеристикой. Проанализированы статические и динамические характеристики путем компьютерного моделирования где показано, что погрешности масштаба буферов напряжений и масштаба-тором напряжения не превышают значений 10 мкВ в диапазоне соответствующего сигнала ± 5 В, а погрешности линейности 300 нВ. Получено переходную характеристику которая гласит, что скорость нарастания выходного напряжения будет не хуже 2000 В/мкс. Проведено сравнение метрологических характеристик буферов напряжения и масштабатором напряжения в виде сово-купности ядер и выходных двухтактных усилителей постоянного тока. Доказано, что применение этих усилителей позволяет суще-ственно (на 3-4 порядка) улучшить нагрузочную способность схем при сохранении уровня входного тока смещения нуля, а также погрешностей масштаба и линейности.; Buffer devices and voltage scalers are widely used in various analog-digital systems, when it is necessary to match the signal in the form of voltage from a low-power sensor to a load, it consumes significantly more power. In this case, the voltage buffer is characterized by a voltage transfer coefficient close to unity, and must also have a high input resistance and sufficient load capacity. The voltage scaler, in contrast to voltage buffers, must additionally provide the necessary gain transfer ratio, which can be substantially more than one. The circuit design features of three variants of the construction of voltage buffer cores and voltage scaling are considered. It is proved that it is advisable to reduce the input zero bias current by using amplifying n-p-n and p-n-p transistors, as well as Shiclay transistors in the input stages. The static and dynamic characteristics of the voltage buffers and the voltage scaler must meet the system requirements of the device. The static characteristics should be attributed primarily to the error of the transfer characteristics of the scale, zero offset and linearity. The dynamics of these devices is determined by the frequency response and transient response. Static and dynamic characteristics are analyzed by computer simulation where it is shown that the scale errors of the voltage buffers and the voltage scaler do not exceed 10 μV in the range of the corre-sponding signal ± 5 V, and the linearity errors are 300 nV. A transient response was obtained which states that the slew rate of the output voltage will be no worse than 2000 V/μs. A comparison of the metrological characteristics of the voltage buffers and the voltage scaler in the form of a set of cores and output push-pull DC amplifiers. It is proved that the use of these amplifiers allows significantly (by 3-4 orders of magnitude) to improve the load capacity of the circuits while maintaining the level of the input zero bias current, as well as scale and lineari-ty errors.
2019-01-01T00:00:00Z