Эффективность и масштабируемость параллельных одношаговых блочных методов решения задачи Коши

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

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2009
Hauptverfasser:	Фельдман, Л.П., Завалкин, Д.А.
Format:	Artikel
Sprache:	Russisch
Veröffentlicht:	Інститут проблем штучного інтелекту МОН України та НАН України 2009
Schlagworte:	Интеллектуальные системы автоматизации научных исследований, проектирования и управления
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/8069
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:	Эффективность и масштабируемость параллельных одношаговых блочных методов решения задачи Коши / Л.П. Фельдман, Д.А. Завалкин // Штучний інтелект. — 2009. — № 3. — С. 258-267— Бібліогр.: 9 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

_version_	1859643398875512832
author	Фельдман, Л.П. Завалкин, Д.А.
author_facet	Фельдман, Л.П. Завалкин, Д.А.
citation_txt	Эффективность и масштабируемость параллельных одношаговых блочных методов решения задачи Коши / Л.П. Фельдман, Д.А. Завалкин // Штучний інтелект. — 2009. — № 3. — С. 258-267— Бібліогр.: 9 назв. — рос.
collection	DSpace DC
description	В статье рассматриваются два семейства параллельных неявных блочных методов решения задачи Коши. Определяется порядок аппроксимации каждого из методов, дается оценка для невязок методов. Для предложенного метода распараллеливания производится построение оценок ускорения, эффективности и масштабируемости. На основании полученных оценок даются рекомендации, при каких условиях данные методы наиболее продуктивны. У статті розглядається дві сім’ї паралельних неявних блокових методів вирішення задачі Коші. Визначається порядок апроксимації кожного з методів, подається оцінка для відхилів методів. Для запропонованого методу розпаралелювання виконується побудова оцінок прискорення, ефективності та здібності до масштабування. На підставі отриманих оцінок даються рекомендації щодо умов, у яких подані методи найбільш продуктивні. Two families of parallel implicit block methods for Cauchy problem solution are considered in this paper. Approximation order and residual estimation of each method are found. For proposed parallelization algorithm parallel speedup, efficiency and scalability estimations are constructed. On the basis of derived estimations guidelines for conditions of method’s using are proposed.
first_indexed	2025-12-07T13:25:02Z
format	Article
fulltext	«Искусственный интеллект» 3’2009 258 5Ф УДК 519.667 Л.П. Фельдман, Д.А. Завалкин Донецкий национальный технический университет, г. Донецк, Украина feldman@r5.dgtu.donetsk.ua, dimzav@gmail.com Эффективность и масштабируемость параллельных одношаговых блочных методов решения задачи Коши В статье рассматриваются два семейства параллельных неявных блочных методов решения задачи Коши. Определяется порядок аппроксимации каждого из методов, дается оценка для невязок методов. Для предложенного метода распараллеливания производится построение оценок ускорения, эффективности и масштабируемости. На основании полученных оценок даются рекомендации, при каких условиях данные методы наиболее продуктивны. Введение Применение высокопроизводительных параллельных вычислительных систем (ВС) является одним из основных направлений развития современной компьютерной науки. Это обстоятельство вызвано не только принципиальным ограничением максимально возможного быстродействия обычных последовательных машин, но и постоянным появлением новых вычислительных задач, для решения которых воз- можностей существующих средств вычислительной техники всегда оказывается недостаточно. Моделирование реальных многомерных динамических процессов, описываемых системами обыкновенных дифференциальных уравнений (СОДУ), и представляет собой класс задач, при реализации которых использование параллельных суперкомпьютеров не только оправдано, но и необходимо. Об этом свидетельствует известный список «большой вызов», в котором такие задачи занимают одно из ведущих мест [1]. Целью данной работы является анализ двух семейств классических параллельных одношаговых блочных методов, в том числе сравнительный анализ их характеристик: сначала осуществляется оценка невязок, на основе которой для методов с одинаковым порядком аппроксимации осуществляется оценка ускорения, эффективности и масштабируемости. Задача Коши Задача Коши для системы обыкновенных дифференциальных уравнений (СОДУ) первого порядка с известными начальными условиями имеет вид (1). Существует много параллельных методов решения задачи Коши для СОДУ первого порядка. В данной статье мы рассмотрим два метода – канонические одношаговые блочные методы и одношаговые блочные методы, предложенные Т.А. Биккартом в [2], в даль- нейшем для краткости мы будем их называть методом «типа Биккарта». Эффективность и масштабируемость параллельных одношаговых блочных методов… «Штучний інтелект» 3’2009 259 5Ф              .)(),,...,,;()( ... ,)(),,...,,;()( ,)(),,...,,;()( 0021 2002212 2 1001211 1 mmmm m m m yxyyyyxf dx xdy yxyyyyxf dx xdy yxyyyyxf dx xdy (1) Прежде чем приступить к описанию методов, введем некоторые обозначения. Множество S точек равномерной сетки { }qt , 1,q Q и st T с шагом  разобьем на N блоков, содержащих k точек каждый, при этом k N Q  . В каждом блоке введем номер точки 0,i k и обозначим через ,n it точку n блока с номером i . Точку ,0nt назовем началом блока n , а ,n kt – концом блока. Очевидно, что имеет место , 1,0n k nt t  . Условимся начальную точку 0 1,0t t в блок не включать. При численном решении задачи Коши для каждого следующего блока новые k значений функции вычисляются одновременно. ... ... ...  B lock 1 B lock n t 1 ,0 t 1 ,1 t 1 ,2 t 1,k -1 t 1 ,k = t 2 ,0 t 2,1 t n-1 ,k t n ,1 t n 2 t n ,k ... Рисунок 1 – Схема разбиения на блоки для одношагового k-точечного метода Пусть un,0 – приближенное значение решения задачи Коши (1) в точке tn,0 – начальной точке обрабатываемого блока. Предполагается, что в пределах одного блока точки сетки находятся на равных расстояниях: kiitt nn ,1,0,   . Канонические одношаговые блочные методы Уравнения канонических одношаговых разностных блочных методов для блока из k точек при использовании вычисленного значения приближенного решения в последнем предшествующем блоку узле, с учетом введенных выше обозначений можно записать в виде (2).          k 1j jn,ji,n,0in,0in, FaFbфiuu , ki ,1 , ,,1 Nn  (2) где  jnnjn ujtfF ,, , . Одношаговые блочные методы «типа Биккарта» Уравнения одношаговых разностных блочных методов «типа Биккарта» для блока из k точек при использовании вычисленного значения приближенного реше- ния в последнем предшествующем блоку узле, с учетом введенных выше обозна- чений можно записать в виде (3). Фельдман Л.П., Завалкин Д.А. «Искусственный интеллект» 3’2009 260 5Ф in k 0j jn,ji, Fua ф 1 ,         , ki ,1 , ,,1 Nn  (3) где  innin uitfF ,, , . Анализ невязок методов Построим невязки для двухточечного канонического блочного метода (4) и двухточечного метода «типа Биккарта» (5).  (4) 3 4 ,1 4 ,2 1= [ ] 24 = [ ] . n n n r x t O r O     (4)     (3) 2 3 ,1 (3) 2 3 ,2 1= [ ] 6 1= [ ] 3 n n n n r x t O r x t O        . (5) Из (4) и (5) видно, что двухточечный канонический блочный метод и двухточечный метод «типа Биккарта» имеют различные порядки аппроксимации, т.е. заведомо известно, что точность результатов этих двух методов будет различной. Для того чтобы сравнивать методы, нам необходимо, чтобы они имели один порядок аппроксимации. Возьмем трехточечный метод «типа Биккарта» (6).       (4) 3 4 ,1 (4) 3 4 ,2 (4) 3 4 ,3 1= [ ] 12 1= [ ] 12 1= [ ] 4 n n n n n n r x t O r x t O r x t O            . (6) Как мы видим из (4) и (6), трехточечный метод «типа Биккарта» имеет тот же порядок аппроксимации, что и двухточечный канонический блочный метод. Ана- логично можно проверить, что трехточечный канонический блочный метод и четы- рехточечный метод «типа Биккарта» имеют один порядок аппроксимации и т.д. Мы получаем, что у канонического блочного метода в блоке k точек, а у метода «типа Биккарта» 1k  точка. Введем условие, что у обоих методов размер блока одина- ковый (рис. 2), тогда мы получим соотношение (7). Рисунок 2 – Вычислительные сетки для двухточечного канонического блочного метода и трехточечного метода «типа Биккарта» ord bick bick Эффективность и масштабируемость параллельных одношаговых блочных методов… «Штучний інтелект» 3’2009 261 5Ф 1 1 1 ord ord bick bick ord bick ord ord bick ord ord k k k k k k k k                . (7) Общий вид уравнения невязки имеет вид (8). 1( )k k nr C x t    , где 1, max i i k C C   . (8) Из (8) для методов одного порядка аппроксимации с учетом (7) отношение невязок двух методов имеет вид (9). 1 1 kk k ord ord ord ord ord ord kk bick bick bick bick bick ord r C C C k r C C C kk k                 . (9) Отношения невязок методов для 2 6k   представлены в табл. 1. Таблица 1 – Отношения невязок методов для 2 6k   k 2 3 4 5 6 ord bick r r 3 8 4 9 1125 4096 99 250 4621925 20155392 Так как мы положили, что блоки сетки в обоих методах равны, то в дальнейшем для упрощения записи мы можем дальнейшие вычисления и оценки делать не для n блоков сетки, а для одного блока. Топологии сети передачи данных Уравнения одношаговых разностных блочных методов «типа Биккарта» для блока из k точек при использовании вычисленного значения приближенного решения в последнем предшествующем блоку узле, с учетом введенных выше обозначений можно записать в виде (3). Параллельные ВС имеют в своем составе поле процессоров, а также один или несколько модулей памяти. Эти функциональные компоненты должны быть связаны через соответствующие коммутационные системы. В силу специфики задач, решаемых на параллельных ВС [3], структура линий связи (топология сети передачи данных) должна удовлетворять различным требованиям. Во-первых, должна обеспечиваться связь между двумя любыми процессорами или модулями. Кроме этого, должно поддерживаться максимальное количество одновременных связей, чтобы средства коммутации не ограничивали параллельную обработку информации. К числу типовых топологий обычно относят следующие схемы: линейка/кольцо, решетка/тор, гиперкуб [4]. Так как в последнее время наиболее распространены топо- логии решетка-тор и гиперкуб, мы будем проводить анализ методов для этих двух топологий. Фельдман Л.П., Завалкин Д.А. «Искусственный интеллект» 3’2009 262 5Ф Решетка (матрица, сетка – mesh) представляет собой систему, в которой процессоры расположены в виде правильной двумерной решетки и каждый процессор (кроме крайних) соединен с четырьмя соседями. Если в решетке граничные про- цессоры соединить линиями связи, то получится замкнутый вариант решетки или тор. Торроидальные 2D-схемы соединения имеют диаметр, пропорциональный p [5]. Структура гиперкуб (hypercube) является частным случаем решетки, когда по каждой размерности сетки имеется только два процессора [4]. То есть гиперкуб содержит Np 2 процессоров при размерности N . При гиперкубовой архитектуре число связей между процессорами небольшое: в N -мерном гиперкубе каждый процессор имеет N соседей. Небольшим по сравнению с числом процессоров оказывается и диаметр систе- мы, равный p2log . Топология гиперкуб предоставляет возможность моделировать некоторые важные типы связей: линейка, кольцо, решетка. Недостатком описанной архитектуры является существование практического предела увеличения размер- ности гиперкуба. Для оценки времени выполнения операции передачи одного сообщения объемом V байт между двумя процессами, локализованными на различных процес- сорах при распределенной памяти, используется следующая линейная модель, пред- ложенная Хокни [6]: B ytlVttT wwspp  , , (10) где st – латентность, длительность подготовки сообщения для передачи; l – длина маршрута; wt – время передачи одного байта; y – число байт в слове; B – пропускная способность канала передачи данных (байт/секунда). Рассмотрим три коммуникационные операции: 1) передача данных между двумя процессорами сети – операция типа «точка- точка»; 2) передача данных от одного процессора всем остальным процессорам сети – операция «один-всем», или «one-to-all»; 3) передача данных от всех процессоров сети всем процессорам сети – множествен- ная пересылка «все-всем», или «all-to-all». Трудоемкость одиночной операции пересылки данных между двумя процессорами может быть получена путем подстановки длины максимального пути (диаметра сети) в выражение (10). Для вычисления времени выполнения множественной пере- сылки необходимо выбрать алгоритм маршрутизации. К числу наиболее рас- пространенных оптимальных алгоритмов передачи данных относятся методы поко- ординатной маршрутизации [4]. Идея этих методов заключается в том, что поиск путей передачи данных осуществляется последовательно для каждой размерности рас- сматриваемой топологии. Для топологии решетка-тор (рис. 3 а) одиночная операция пересылки данных требует следующего времени (11) для исполнения с учетом модели (10) и диаметра топологии.  2/2 ptVtT ws M pp  . (11) Эффективность и масштабируемость параллельных одношаговых блочных методов… «Штучний інтелект» 3’2009 263 5Ф Пересылка данных от одного процессора всем остальным в условиях топологии тор может быть получена из этого же способа передачи для кольцевой топологии, выполненного в два этапа (12). 2 / 2M one to all s wT t V t p         . (12) Множественная рассылка сообщений также может быть выполнена при помо- щи алгоритма, получаемого обобщением способа передачи данных для кольцевой структуры сети на основе идеи покоординатной маршрутизации (13). )1()1(2  ptVptT ws M alltoall . (13) Для топологии гиперкуб (рис. 3 б) время выполнения одиночной операции пере- сылки данных равно (14). ptVtT ws H pp 2log . (14) Время выполнения операции передачи данных от одного процессора всем осталь- ным в топологии гиперкуб выражается формулой (15).   ptVtT ws H alltoone 2log . (15) Алгоритм выполнения множественной рассылки сообщений для гиперкуба может быть получен путем обобщения способа передачи данных «все-всем» для топологии решетка на размерность гиперкуба plp 2log . Каждому процессору ставится в соответствие двоичный эквивалент его номера. Процессоры, имеющие непосредственное соединение в гиперкубе, будут иметь номера, отличающиеся друг от друга только одним разрядом. На каждом этапе lpii ,1,  алгоритма функцио- нируют все процессоры сети, которые обмениваются данными со своими соседями по i размерности и формируют объединенные сообщения (16).      lp i wsw i s H alltoall pVtpttVtT 1 2 1 )1(log)2( . (16) Алгоритм распараллеливания Рассмотрим простейший в реализации метод распараллеливания – распараллели- вание по уравнениям вычислительной схемы метода. Пусть в нашей вычислительной системе p процессоров, а система уравнений, для которой решается задача Коши, имеет m уравнений. Тогда на каждом процессоре в нашем алгоритме распаралле- ливания будут вычисляться p m уравнений для всех k точек текущего блока. После того как эти значения вычислены, каждый процессор рассылает значения в последней точке блока каждого своего уравнения остальным процессорам, т.е. происходит обмен типа «все-всем». Считая, что мы работаем с 8-байтными числами, согласно модели Хокни мы получаем время обмена для 1 блока сетки для топологии решетка- тор (17), а для топологии гиперкуб соответственно (18). )1(8)1(2  pt p mptT ws M alltoall , (17) )1(8log2  p p mtptT ws H alltoall . (18) Фельдман Л.П., Завалкин Д.А. «Искусственный интеллект» 3’2009 264 5Ф Анализ ускорения и эффективности Обозначим через m количество уравнений в исходной системе, через  – время выполнения одной операции с плавающей точкой, а через ( )fT  – сложность правой части, т.е. время вычисления ( , )F x t . Будем считать, что для нахождения решения во всех k точках блока с заданной точностью достаточно k итераций. С учетом введенных обозначений и предположения, мы получим, что время последовательного вычисления всех точек одного блока каноническим блочным методом выражается формулой (19), а методом «типа Биккарта» – выражением (20). (T ( ) (2 4) )ord s fT k k k k m          , (19)   2 T ( ) 2 4bick s fT k k k k m          . (20) Время параллельного вычисления всех точек одного блока с использованием пред- ложенного алгоритма распараллеливания каноническим блочным методом выра- жается формулой (21) для топологии решетка-тор и (22) для топологии гиперкуб, а методом «типа Биккарта» – выражением (23) для топологии решетка-тор и (24) для топологии гиперкуб соответственно.  (T ( ) (2 4) ) 2 t 1 8 t ( 1)ord p mesh f s w m mT k k k k p p p p                    , (21) 2(T ( ) (2 4) ) t log 8 t ( 1)ord p hcube f s w m mT k k k k p p p p                   , (22)     2T ( ) 2 4 2 t 1 8 t ( 1)bick p mesh f s w m mT k k k k p p p p                    , (23)   2 2T ( ) 2 4 t log 8 t ( 1)bick p hcube f s w m mT k k k k p p p p                   . (24) В случае простой правой части ( )fT  ускорение и эффективность обоих методов очень малы, поэтому рассмотрим случай достаточно сложной правой части ( ) 1000fT    . Значения  , st , wt были взяты из [4], они являются реальными значениями, измеренными для кластера Нижегородского государственного универ- ситета. Количество процессоров p возьмем равным 512. 100 200 300 400 500 m0 20 40 60 80 100 S 100 200 300 400 500 m0.00 0.05 0.10 0.15 0.20 E а) б) 6-точечный канонический 7-точечный «типа Биккарта» Рисунок 3 – Ускорение а) и эффективность б) канонического одношагового блочного метода и метода «типа Биккарта» для топологии решетка-тор Эффективность и масштабируемость параллельных одношаговых блочных методов… «Штучний інтелект» 3’2009 265 5Ф Построив графики ускорения и эффективности, легко увидеть, что для обеих рассматриваемых топологий и обоих рассматриваемых методов с ростом количества точек в методе улучшаются характеристики и ускорения, и эффективности. Сравним ускорение (рис. 3 а, рис. 4 а) и эффективность (рис. 3 б, рис. 4 б) наилучшего из пред- ставленных канонических одношаговых блочных методов и наилучшего из представ- ленных методов «типа Биккарта» для обеих топологий. 100 200 300 400 500 m0 50 100 150 200 250 S 100 200 300 400 500 m0.0 0.2 0.4 0.6 0.8 1.0 E а) б) 6-точечный канонический 7-точечный «типа Биккарта» Рисунок 4 – Ускорение а) и эффективность б) канонического одношагового блочного метода и метода «типа Биккарта» для топологии гиперкуб Анализ масштабируемости Постановка вопроса об оценке эффективности распараллеливания при увеличении числа процессоров с сохранением объема вычислений не всегда является целью иссле- дований, более того, некоторыми авторами [7] считается спорной. Действительно, при изменении числа процессоров эффективность параллельного алгоритма зависит как от свойств самой топологии сети, так и от того, насколько хорошо данный алгоритм под- ходит для данной топологии, насколько удачно он использует ее лучшие стороны. По- этому нельзя исследовать масштабируемость параллельного алгоритма абстрактно, в отрыве от топологии сети. Мы будем исследовать масштабируемость параллельных алгоритмов с помощью математического аппарата теории изоэффективного анализа [8], [9]. Для построения функции изоэффективности необходимо определить общие накладные расходы на парал- лельный алгоритм, для обоих алгоритмов они у нас будут одинаковыми вследствие выбранного алгоритма распараллеливания. Для топологии решетка-тор эти расходы выражаются формулой (25), а для топологии гиперкуб – формулой (26).  2 t 1 8 t ( 1) ,mesh o s wT p p m p          (25) 2T = t log 8 t ( 1) .hcube o s wp p m p       (26) Основное соотношение изоэффективного анализа [9] имеет вид (27). s oT K T  , (27) где 1 EK E   . (28) Фельдман Л.П., Завалкин Д.А. «Искусственный интеллект» 3’2009 266 5Ф Тогда основное соотношение изоэффективного анализа для канонического одношагового блочного метода для топологии решетка-тор принимает вид (29), а для топологии гиперкуб – (30). Аналогично для метода «типа Биккарта» для топологии решетка-тор имеем (31), а для топологии гиперкуб – (32).   2 (2 (2 ) T ( )) 2 1 t 8 ( 1) tf s wk m k k K p p m p                 , (29)  2 2 (2 (2 ) T ( )) 8 log( 1) t sf wk m k k K p pm tp                , (30)      2 24 2 T ( ) 2 1 t 8 ( 1) tf s wk m k k K p p m p                 , (31)     2 2 2 l4 2 T ( ) 8 ( 1) t ogf w sk m k k K m p p t p                . (32) Так как количество точек в блоке 2,7k  и мы рассматриваем случай систем с большим количеством уравнений m k и сложной правой частью ( )fT k  , а также с учетом того, что мы полагаем p m всегда, то выражения (29) – (32) можно преобразовать к виду (33) – (36) соответственно. 3 2 T ( ) T ( ) f w f s m K m p t m K p t               , (33) , (34) 3 2 T ( ) T ( ) f w f s m K m p t m K p t               , (35) 2 T ( ) T ( ) log f w f s m K m p t m K p p t              . (36) Как мы видим, для обоих видов топологий и обоих видов методов основное соотношение изоэффективного анализа принимает один и тот же вид (37). T ( ) .f wm K m p t    (37) Из соотношения (37) следует, что при увеличении количества процессоров для сохранения постоянной эффективности можно увеличивать не только количество уравнений m системы, но и сложность правой части T ( )f  . Выводы Канонические одношаговые блочные методы и методы «типа Биккарта» по причине использования одинакового метода распараллеливания обладают одинаковой масштаби- руемостью. Чем сложнее правая часть уравнения T ( )f  , тем большее ускорение и эффек- тивность показывают оба метода. Как видно из рис. 3 – 4 а) и б), ускорение и эффектив- ность 6-точечного канонического блочного метода (наилучшего из рассмотренных кано- нических одношаговых методов) выше, чем ускорение и эффективность 7-точечного метода «типа Биккарта», при этом оба метода обладают одинаковым порядком аппроксимации. Как видно из табл. 1, при сравнении пар методов, обладающих одним по- Эффективность и масштабируемость параллельных одношаговых блочных методов… «Штучний інтелект» 3’2009 267 5Ф рядком аппроксимации, оказывается, что у канонического одношагового метода в каждой из пар невязка меньше, т.е. метод является более точным, в то же время его ускорение и эффективность выше, чем у метода «типа Биккарта» того же порядка аппроксимации. Учитывая это, а также то, что масштабируемость обоих методов одинакова за счет выбранного алгоритма распараллеливания, канонические одношаговые методы оказыва- ются в целом лучше методов «типа Биккарта». Литература 1. Grand Challenges: High performance computing and communications // A report by the Committee on Physical, Mathematical and Engineering Science, NSF/CISE, 1800 G. Street NW, Washington, DC 20550, 2001. 2. Sloate H.M. A-Stable Composite Multistep Methods / H.M. Sloate, T.A. Bickart // Journal of the Association for Computing Machinery. – 1973. – Vol. 20, № 1. 3. Гергель В.П. Основы параллельных вычислений для многопроцессорных вычислительных систем / В.П. Гергель, Р.Г. Стронгин. – Н. Новгород : ННГУ, 2001. – 122 c. 4. Гергель В.П. Теория и практика параллельных вычислений / Гергель В.П. – Москва : Бином. Лаборатория знаний, 2007. – 423 с. 5. Малиновский Б.Н. Вопросы построения высокопроизводительных средств обработки информации / Б.Н. Малиновский, В.П. Боюн, Л.Г. Козлов // Управляющие системы и машины. – 1976. – № 6. – С. 19-22. 6. Хокни Р. Параллельные ЭВМ: Архитектура, программирование и алгоритмы / Р. Хокни, К. Джессхоуп. – М. : Радио и связь, 1986. – 392 с. 7. Забродин А.В. Параллельные вычислительные технологии. Состояние и перспективы // Материалы I молодежной школы «Высокопроизводительные вычисления и их приложения» [Электронный ресурс] / А.В. Забродин. – Режим доступа : ftp://parallel.ru/parallel/chg1999. 8. Gupta A. Scalability of parallel algorithm for matrix multiplication / A. Gupta, V. Kumar // Technical report TR- 91-54, Department of CSU of Minneapolis, 1994. 9. Kumar V. Scalability of Parallel Algorithms for the All-Pairs Shortest Path Problem / V. Kumar, V. Singh // Technical report, Department of CSU of Minneapolis, 1991. Л.П. Фельдман, Д.О. Завалкін Ефективність та здібність до масштабування паралельних блокових однокрокових методів вирішення задачі Коші У статті розглядається дві сім’ї паралельних неявних блокових методів вирішення задачі Коші. Визначається порядок апроксимації кожного з методів, подається оцінка для відхилів методів. Для запропонованого методу розпаралелювання виконується побудова оцінок прискорення, ефективності та здібності до масштабування. На підставі отриманих оцінок даються рекомендації щодо умов, у яких подані методи найбільш продуктивні. L.P. Feldman, D.A. Zavalkin Efficiency and Scalability of Parallel Block One-Step Methods for Cauchy Problem Solution Two families of parallel implicit block methods for Cauchy problem solution are considered in this paper. Approximation order and residual estimation of each method are found. For proposed parallelization algorithm parallel speedup, efficiency and scalability estimations are constructed. On the basis of derived estimations guidelines for conditions of method’s using are proposed. Статья поступила в редакцию 01.06.2009.
id	nasplib_isofts_kiev_ua-123456789-8069
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
issn	1561-5359
language	Russian
last_indexed	2025-12-07T13:25:02Z
publishDate	2009
publisher	Інститут проблем штучного інтелекту МОН України та НАН України
record_format	dspace
spelling	Фельдман, Л.П. Завалкин, Д.А. 2010-04-29T09:57:43Z 2010-04-29T09:57:43Z 2009 Эффективность и масштабируемость параллельных одношаговых блочных методов решения задачи Коши / Л.П. Фельдман, Д.А. Завалкин // Штучний інтелект. — 2009. — № 3. — С. 258-267— Бібліогр.: 9 назв. — рос. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/8069 519.667 В статье рассматриваются два семейства параллельных неявных блочных методов решения задачи Коши. Определяется порядок аппроксимации каждого из методов, дается оценка для невязок методов. Для предложенного метода распараллеливания производится построение оценок ускорения, эффективности и масштабируемости. На основании полученных оценок даются рекомендации, при каких условиях данные методы наиболее продуктивны. У статті розглядається дві сім’ї паралельних неявних блокових методів вирішення задачі Коші. Визначається порядок апроксимації кожного з методів, подається оцінка для відхилів методів. Для запропонованого методу розпаралелювання виконується побудова оцінок прискорення, ефективності та здібності до масштабування. На підставі отриманих оцінок даються рекомендації щодо умов, у яких подані методи найбільш продуктивні. Two families of parallel implicit block methods for Cauchy problem solution are considered in this paper. Approximation order and residual estimation of each method are found. For proposed parallelization algorithm parallel speedup, efficiency and scalability estimations are constructed. On the basis of derived estimations guidelines for conditions of method’s using are proposed. ru Інститут проблем штучного інтелекту МОН України та НАН України Интеллектуальные системы автоматизации научных исследований, проектирования и управления Эффективность и масштабируемость параллельных одношаговых блочных методов решения задачи Коши Ефективність та здібність до масштабування паралельних блокових однокрокових методів вирішення задачі Коші Efficiency and Scalability of Parallel Block One-Step Methods for Cauchy Problem Solution Article published earlier
spellingShingle	Эффективность и масштабируемость параллельных одношаговых блочных методов решения задачи Коши Фельдман, Л.П. Завалкин, Д.А. Интеллектуальные системы автоматизации научных исследований, проектирования и управления
title	Эффективность и масштабируемость параллельных одношаговых блочных методов решения задачи Коши
title_alt	Ефективність та здібність до масштабування паралельних блокових однокрокових методів вирішення задачі Коші Efficiency and Scalability of Parallel Block One-Step Methods for Cauchy Problem Solution
title_full	Эффективность и масштабируемость параллельных одношаговых блочных методов решения задачи Коши
title_fullStr	Эффективность и масштабируемость параллельных одношаговых блочных методов решения задачи Коши
title_full_unstemmed	Эффективность и масштабируемость параллельных одношаговых блочных методов решения задачи Коши
title_short	Эффективность и масштабируемость параллельных одношаговых блочных методов решения задачи Коши
title_sort	эффективность и масштабируемость параллельных одношаговых блочных методов решения задачи коши
topic	Интеллектуальные системы автоматизации научных исследований, проектирования и управления
topic_facet	Интеллектуальные системы автоматизации научных исследований, проектирования и управления
url	https://nasplib.isofts.kiev.ua/handle/123456789/8069
work_keys_str_mv	AT felʹdmanlp éffektivnostʹimasštabiruemostʹparallelʹnyhodnošagovyhbločnyhmetodovrešeniâzadačikoši AT zavalkinda éffektivnostʹimasštabiruemostʹparallelʹnyhodnošagovyhbločnyhmetodovrešeniâzadačikoši AT felʹdmanlp efektivnístʹtazdíbnístʹdomasštabuvannâparalelʹnihblokovihodnokrokovihmetodívviríšennâzadačíkoší AT zavalkinda efektivnístʹtazdíbnístʹdomasštabuvannâparalelʹnihblokovihodnokrokovihmetodívviríšennâzadačíkoší AT felʹdmanlp efficiencyandscalabilityofparallelblockonestepmethodsforcauchyproblemsolution AT zavalkinda efficiencyandscalabilityofparallelblockonestepmethodsforcauchyproblemsolution

Эффективность и масштабируемость параллельных одношаговых блочных методов решения задачи Коши

Institution

Ähnliche Einträge