Пути и методы повышения быстродействия сложных вычислений

В данной статье описаны возможные пути и методы повышения быстродействия сложных вычислений за счет оптимизации взаимодействия операционной системы и вычислительных алгоритмов....

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2013
Hauptverfasser:	Зосимов, В.В., Булгакова, А.С., Тищенко, А.В.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Інститут кібернетики ім. В.М. Глушкова НАН України 2013
Schriftenreihe:	Комп’ютерні засоби, мережі та системи
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/69705
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Пути и методы повышения быстродействия сложных вычислений / В.В. Зосимов, А.С. Булгакова, А.В. Тищенко // Комп’ютерні засоби, мережі та системи. — 2013. — № 12. — С. 27-33. — Бібліогр.: 7 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-69705
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-697052025-02-23T18:13:46Z Пути и методы повышения быстродействия сложных вычислений Ways and methods of increasing complex calculations performance Зосимов, В.В. Булгакова, А.С. Тищенко, А.В. В данной статье описаны возможные пути и методы повышения быстродействия сложных вычислений за счет оптимизации взаимодействия операционной системы и вычислительных алгоритмов. У даній статті описані можливі шляхи і методи підвищення швидкодії складних обчислень за рахунок оптимізації взаємодії операційної системи і обчислювальних алгоритмів. This article describes the ways and methods of improving the performance of complex calculations by optimizing the interaction between the operating system and computer algorithms. 2013 Article Пути и методы повышения быстродействия сложных вычислений / В.В. Зосимов, А.С. Булгакова, А.В. Тищенко // Комп’ютерні засоби, мережі та системи. — 2013. — № 12. — С. 27-33. — Бібліогр.: 7 назв. — рос. 1817-9908 https://nasplib.isofts.kiev.ua/handle/123456789/69705 004.832.3 ru Комп’ютерні засоби, мережі та системи application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
description	В данной статье описаны возможные пути и методы повышения быстродействия сложных вычислений за счет оптимизации взаимодействия операционной системы и вычислительных алгоритмов.
format	Article
author	Зосимов, В.В. Булгакова, А.С. Тищенко, А.В.
spellingShingle	Зосимов, В.В. Булгакова, А.С. Тищенко, А.В. Пути и методы повышения быстродействия сложных вычислений Комп’ютерні засоби, мережі та системи
author_facet	Зосимов, В.В. Булгакова, А.С. Тищенко, А.В.
author_sort	Зосимов, В.В.
title	Пути и методы повышения быстродействия сложных вычислений
title_short	Пути и методы повышения быстродействия сложных вычислений
title_full	Пути и методы повышения быстродействия сложных вычислений
title_fullStr	Пути и методы повышения быстродействия сложных вычислений
title_full_unstemmed	Пути и методы повышения быстродействия сложных вычислений
title_sort	пути и методы повышения быстродействия сложных вычислений
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2013
url	https://nasplib.isofts.kiev.ua/handle/123456789/69705
citation_txt	Пути и методы повышения быстродействия сложных вычислений / В.В. Зосимов, А.С. Булгакова, А.В. Тищенко // Комп’ютерні засоби, мережі та системи. — 2013. — № 12. — С. 27-33. — Бібліогр.: 7 назв. — рос.
series	Комп’ютерні засоби, мережі та системи
work_keys_str_mv	AT zosimovvv putiimetodypovyšeniâbystrodejstviâsložnyhvyčislenij AT bulgakovaas putiimetodypovyšeniâbystrodejstviâsložnyhvyčislenij AT tiŝenkoav putiimetodypovyšeniâbystrodejstviâsložnyhvyčislenij AT zosimovvv waysandmethodsofincreasingcomplexcalculationsperformance AT bulgakovaas waysandmethodsofincreasingcomplexcalculationsperformance AT tiŝenkoav waysandmethodsofincreasingcomplexcalculationsperformance
first_indexed	2025-11-24T08:09:35Z
last_indexed	2025-11-24T08:09:35Z
_version_	1849658468189863936
fulltext	Комп’ютерні засоби, мережі та системи. 2013, № 12 27 V.V. Zosimov, O.S. Bulgakova, A.V. Tyshchenko WAYS AND METHODS OF INCREASING COMPLEX CALCULATIONS PERFORMANCE This article describes the ways and methods of improving the perfor- mance of complex calculations by optimizing the interaction between the operating system and computer algorithms. Key words: operating system, com- puter algorithm, the universal task schedulers. У даній статті описані можливі шляхи і методи підвищення шви- дкодії складних обчислень за раху- нок оптимізації взаємодії опера- ційної системи і обчислювальних алгоритмів. Ключові слова: операційна систе- ма, ком’ютерний алгоритм, уні- версальні планувальники задач. В данной статье описаны воз- можные пути и методы повыше- ния быстродействия сложных вычислений за счет оптимизации взаимодействия операционной системы и вычислительных алго- ритмов. Ключевые слова: операционная система, компьютерный алго- ритм, универсальные планиров- щики задач. © В.В. Зосимов, А.С. Булгакова, А.В. Тищенко, 2013 УДК 004.832.3 В.В. ЗОСИМОВ, А.С. БУЛГАКОВА, А.В. ТИЩЕНКО ПУТИ И МЕТОДЫ ПОВЫШЕНИЯ БЫСТРОДЕЙСТВИЯ СЛОЖНЫХ ВЫЧИСЛЕНИЙ Введение. В настоящее время во многих сферах человеческой деятельности приме- няются ресурсоемкие научные расчеты для анализа данных и прогнозирования явлений и событий различного характера. Для более эффективного ведения исследований созда- ются международные исследовательские группы, в которых задействованы специали- сты из различных областей знаний. Такое междисциплинарное взаимодействие позво- ляет участникам группы взглянуть на про- блему под разными углами и помочь друг другу увидеть пути решения, не очевидные каждому отдельному специалисту. Не смотря на эффективность сотрудничества таких групп, в их работе могут возникнуть перебои связанные, в том числе, и с низкой скоро- стью обработки полученных в ходе исследо- вания данных. В таких группах каждый уче- ный занимается своей частью общей пробле- мы. Сложность решаемых каждым из членов группы задач может быть различна и зачас- тую одним членам группы приходится ждать результаты расчетов других членов группы для перехода к следующему этапу исследо- вания [1]. Частое возникновение таких за- держек может отодвинуть выполнение про- екта на месяцы. Кроме того, задержки и про- стои в работе могут негативно сказаться на слаженности и заинтересованности работы группы в проекте. Поэтому актуальной явля- ется задача повышения быстродействия ре- сурсоемких научных вычислений за счет оп- тимизации механизмов взаимодействия про- граммного кода алгоритма и операционной системы. В.В. ЗОСИМОВ, А.С. БУЛГАКОВА, А.В. ТИЩЕНКО Комп’ютерні засоби, мережі та системи. 2013, № 12 28 Основная часть. Научные расчеты ведутся как на персональных компьюте- рах с многоядерными процессорами, так и на специализированных вычисли- тельных кластерах с большим количеством ядер. Большая часть этих вычисли- тельных систем работает под управлением операционной системы Linux. Одной из основных частей операционной системы является планировщик задач, кото- рый предназначен для распределения инициируемых запущенными приложе- ниями потоков между процессорными ядрами, а также для обеспечения много- задачности, отсутствия зависаний системы и ускорения выполнения запущен- ных потоков [2–4]. В настоящее время в Linux используются универсальные планировщики задач, в которых наибольшим приоритетом обладают интерак- тивные задачи взаимодействия пользователя с интерфейсом операционной сис- темы. Поступающие в систему задачи по уровню приоритета подразделяются на K типов. Приоритет ξk каждого типа задачи может определяться номером k ее типа или величиной, пропорциональной k. Коэффициент пропорциональности удобно выбрать из условия, чтобы сумма приоритета задач всех типов была нормирова- на на 1: .1 K 1k k =ξ∑ = (1) Помимо того, что каждая задача относится к некоторому типу, она также принадлежит одному из 2-х классов. В первый класс входят обычные задачи. Второй класс составляют задачи, решение которых требует проведения зна- чительно большего количества операций (так называемые «счетные задачи»). Процесс решения счетных задач занимает значительно большее время. Общее количество счетных задач примерно на порядок меньше общего количества обычных задач. Таким образом, каждая задача характеризуется парой целых чисел (тип, класс). Принимается, что потоки задач всех типов на входе системы – случайные и квазистационарные, а законы распределения количеств поступающих на вход задач – показательные. То есть функция распределения F(t) величины проме- жутка времени t между поступлениями двух задач одного типа определяется как 𝐹(𝑡) = 1 − 𝑒𝑥𝑝{−𝑡/𝑇𝑘�𝜏} �, (2) где Tk – среднее время между поступлениями двух задач одного типа. В общем случае величины Tk(τ) различны для разных типов задач и зависят от системного времени τ (текущее время суток). Свойство квазистационарности потоков означает, что интенсивность посту- пления задач в систему может слабо изменяться в течении времени порядка 1000 с, но в каждый момент τ законы распределения промежутков времени меж- ду поступлениями очередных задач показательные. В течении рабочего дня су- ПУТИ И МЕТОДЫ ПОВЫШЕНИЯ … Комп’ютерні засоби, мережі та системи. 2013, № 12 29 ществует некоторый характерный профиль спроса на время процессора, имею- щий несколько максимумов и минимумов. Для решения задач требуется N типов ресурсов. Потребности задач в ресур- сах определяются матрицами R = Rij; i = 1,N; j = 1,K и σ = σij, i = 1,N; j = 1,K. Элементы R определяют среднюю потребность (математическое ожидание) k-й задачи в n-м ресурсе [5]. Современные алгоритмы разработаны для обеспечения максимально ком- фортной работы пользователей и ориентированы в основном на использование в домашних и офисных компьютерах. То есть современные планировщики ориен- тированы на запуск в компьютере большого количества различных приложений, между которыми осуществляется регулярное переключение [6, 7]. Это делает их малоэффективными при работе с ресурсоемкими научными вычислениями, где основная часть потоков занята вычислительными задачами, а взаимодействие пользователя с интерфейсом операционной системы сведено к минимуму. Кроме того, есть ряд особенностей, снижающих эффективность существующих плани- ровщиков при работе с ресурсоемкими научными вычислениями: - существующие планировщики способны разделять задачи на интерактив- ные, вычислительные и т. д. Но идентифицируя задачу как вычислительную, планировщик не может получить дополнительную информацию о запущенном вычислении и этапе конкретного вычисления задачи; - для обеспечения многозадачности и высокой скорости реакции интерфейса на действия пользователя существующие планировщики запускают на выполне- ние одновременно несколько потоков на одном ядре. Ядро в один момент вре- мени выполняет только один поток. Поэтому для обеспечения параллельной ра- боты запущенных приложений происходит регулярное переключение между потоками, работающими одновременно на одном ядре. Переключение между потоками является довольно трудоемкой задачей, а так как переключений осу- ществляется достаточно много, то большой процент процессорного времени расходуется именно на них. В вычислительных алгоритмах существуют этапы, которые не могут быть распараллелены, т. е. для выполнения текущей операции необходим всего один поток. Например, считывание исходных данных, вывод результатов, передача результатов вычислений текущего этапа работы алгоритма на следующий. Так- же есть этапы непосредственно вычислений, которые могут быть распараллеле- ны, так как каждое отдельное вычисление является отдельной задачей, а соот- ветственно, для нее будет создан отдельный поток. Количество времени, необ- ходимое на проведение каждого расчета, может быть различно, и задача плани- ровщика задач операционной системы – максимально эффективно распределить вычислительные потоки между процессорными ядрами для минимизации вре- мени ожидания каждого ядра и накладных расходов на переключение между задачами. Для повышения скорости работы алгоритмов научных расчетов существует несколько путей: В.В. ЗОСИМОВ, А.С. БУЛГАКОВА, А.В. ТИЩЕНКО Комп’ютерні засоби, мережі та системи. 2013, № 12 30 - увеличение количества единиц в вычислительном кластере. Как правило, ресурсоемкие научные вычисления ведутся не на одном компьютере, а на спе- циально подготовленных вычислительных кластерах. Наиболее простым и оче- видным способом увеличения скорости расчетов является наращивание вычис- лительной мощности кластера за счет увеличения количества компьютеров. Не смотря на очевидность и простоту реализации, такой подход обладает рядом минусов. Основной минус – дополнительные материальные расходы на покупку и размещение дополнительных компьютеров. Но необходимо учитывать, что увеличение количества процессоров в вычислительном кластере далеко не все- гда может способствовать повышению скорости ведения расчетов. Это происхо- дит потому, что в алгоритмах расчетов не все части задачи могут быть распа- раллелены. А если задачи распараллелены на некоторое ограниченное количест- во ядер, то увеличение количества параллельных процессов не будет иметь смысла, так как приведет к ожиданию завершения работы одних процессов дру- гими и простаиванию выделенных под них ядер. Таким образом высокие мате- риальные затраты могут дать только незначительный прирост производительно- сти, а в некоторых случаях не дать его вовсе. Кроме того, такой подход позволит получить прирост производительности на одном конкретном вычислительном кластере, но никак не повлияет на повышение производительности других; - повышение быстродействия за счет усовершенствования и оптимизации работы алгоритма. Такой подход может помочь повысить быстродействие алго- ритма, но потребует больших временных затрат на исследования в этом направ- лении без гарантии получения каких-либо результатов. В долгосрочной пер- спективе этот подход должен использоваться. Положительные результаты ис- следований могут дать значительный прирост скорости работы алгоритма и этот прирост будет качественно лучше, чем полученный первым способом. Он по- зволит ускорить работу алгоритма не зависимо от используемой вычислитель- ной платформы. Однако такой подход абсолютно не применим к другим алго- ритмам; - оптимизация механизмов взаимодействия операционной системы, процес- сора и вычислительного алгоритма. Все алгоритмы разделяются на небольшие подзадачи, которые планировщик задач операционной системы передает на об- работку процессору. Здесь необходимо разработать механизмы, которые позво- лят максимально эффективно использовать процессорное время при ведении сложных расчетов, что позволит увеличить вычислительную мощность системы независимо от ее конфигурации и используемых алгоритмов. Очевидно, что третий способ в виду своей универсальности является наибо- лее перспективным. Его реализация подразумевает разработку информационной технологии, в которую будут входить несколько модулей: - планировщик задач операционной системы, значительно отличающийся от нынешнего и ориентированный на ведение сложных расчетов при минимальном взаимодействии пользователя с интерфейсом операционной системы. Это по- зволит сократить количество процессорного времени, выделяемого для интерак- тивных задач, которые в существующих планировщиках являются приоритет- ПУТИ И МЕТОДЫ ПОВЫШЕНИЯ … Комп’ютерні засоби, мережі та системи. 2013, № 12 31 ными. При проектировании планировщика необходимо учитывать возможность запуска нескольких расчетов одновременно. Они могут выполняться с выделе- нием всех необходимых ресурсов системы для максимальной скорости работы запущенного первым расчета или в режиме, позволяющем выделять для расче- тов только необходимое для обеспечения приемлемой работы количество ресур- сов в соответствии с очередностью запуска. Это потребует разработки механиз- мов для определения необходимого количества ресурсов для приемлемой рабо- ты алгоритма. Под приемлемой работой следует понимать время расчета, мень- ше максимально возможного, но не превышающего предел ожидания пользова- теля. Необходимость разработки второго способа обусловлена наличием преде- ла ведения параллельных вычислений, после достижения которого выделение под расчет дополнительных ядер все еще будет давать прирост производитель- ности, но начнет быстро увеличиваться суммарное время простоя по всем про- цессорным ядрам. Поэтому дальнейшее выделение ядер под расчет становится нецелесообразным. Гораздо эффективнее выделить эти ядра для другого запу- щенного параллельно расчета, который еще не достиг этого предела. Однако если запустить только один расчет, ядра можно выделять до тех пор, пока растет производительность. Описанные выше механизмы будут частью модуля обучения и адаптации планировщика под конкретные вычислительные алгоритмы. Основной задачей модуля адаптации является минимизация количества пе- реключений между задачами, так как эти операции не являются полезной рабо- той планировщика и при неправильном планировании могут отнимать большой процент ресурсов процессора. Для этого необходим механизм обучения, анали- зирующий работу алгоритма после его завершения, что позволит: - разработать механизмы оценки времени, необходимого для завершения всех переданных на выполнение ядру потоков. Это позволит минимизировать время простоя ядер за счет своевременного перераспределения между ними по- ставленных в очередь на выполнение потоков; - разработать механизмы оценки предполагаемого времени выполнения пе- редаваемого в очередь потока; - разработать механизмы передачи информации о степени завершенности процессов и времени, необходимого для выполнения поставленных в очередь процессов, от приложения планировщику задач; - усовершенствовать алгоритмы передачи данных по сети Ethernet с помо- щью стека протоколов TCP/IP между объединенными в кластер компьютерами. Эти механизмы позволят настроить работу планировщика для каждого кон- кретного алгоритма и тем самым создать класс адаптивных планировщиков за- дач операционной системы Linux с возможностью автоматической оптимизации своих параметров на основе обучения. На рис. 1 показана общая схема взаимодействия операционной системы с планировщиком задач. В.В. ЗОСИМОВ, А.С. БУЛГАКОВА, А.В. ТИЩЕНКО Комп’ютерні засоби, мережі та системи. 2013, № 12 32 РИС. 1. Общая схема взаимодействия операционной системы с планировщиком задач При использовании мощных вычислительных кластеров, где количество ядер превышает количество одновременно инициируемых системой потоков или незначительно ему уступает, необходимость в оптимизации планировщика от- сутствует, так как стандартные планировщики обеспечивают эффективную ра- боту алгоритма, направляя потоки на свободные ядра. Необходимость в оптими- зации работы планировщика возникает в том случае, когда количество ядер зна- чительно меньше числа одновременно инициируемых вычислительных потоков. Это происходит при ведении расчетов на одном многоядерном процессоре, на нескольких компьютерах, объединенных в небольшой вычислительный кластер, например, в пределах одного кабинета, или при запуске на кластере с большим количеством ядер нескольких десятков ресурсоемких вычислений. В последнем случае задача оптимизации работы планировщика усложняется необходимостью не просто ускорения выполнения всех запущенных одновременно потоков, но и учетом того к какому вычислению принадлежат потоки и распределением пото- ков таким образом, чтобы как можно быстрее завершался очередной этап каж- дого расчета и полученные результаты передавались на следующий этап. ПУТИ И МЕТОДЫ ПОВЫШЕНИЯ … Комп’ютерні засоби, мережі та системи. 2013, № 12 33 Выводы. Предложенная информационная технология позволит увеличить производительность вычислительных систем независимо от их конфигурации и используемых алгоритмов. Наиболее эффективным применение этой технологии будет в условиях нехватки вычислительных ресурсов, когда количество иниции- руемых вычислительных потоков будет значительно превышать количество дос- тупных ядер процессоров. 1. Планировщики процессов: http://ck.kolivas.org/patches/staircase-deadline/ rsdl_scheduler. readme 2. Планировщик задач в Linux (proccess cpu kernel linux): http://www.opennet.ru 3. Лав Р. Разработка ядра Linux, 2-е издание / Р. Лав // Пер. с англ. – М.: ООО И.Д. Вильямс, 2006. – 448 с. 4. Fujiyama R., Scherpelz J., Ferlo M. Analyzing the Linux schedulers’s tunables. – 2003. – 19 с. 5. Белоусов С.М. Имитационная модель и методы рационального распределения ресурсов операционной системы : Автореф. дис. канд. техн. наук. – Москва. – 2007. – 24 с. 6. Kolivas C. Linux Kernel CPU Scheduler Contributor, IRC conversations, no transcript, 2004. 7. Jake Moilanen's Linux Kernel Homepage: http://kernel.jakem.net Получено 06.09.2013

Пути и методы повышения быстродействия сложных вычислений

Institution

Ähnliche Einträge