Макроконвейер
Макроконвейер — распределенная многопроцессорная система, обладающая программной и аппаратной поддержкой организации вычислений по макроконвейерному принципу.[1] Этот принцип был предложен в 1978 году советским математиком В. М. Глушковым. Его суть состоит в том, что при распределении вычислительных заданий между процессорами каждому процессору на очередном шаге вычислений дается такое задание, которое может загрузить его работой на определенное время, без взаимодействия с другими процессорами.[1]:320 Последовательное применение принципа макроконвейера позволяет получить линейное ускорение в зависимости от числа процессоров, используемых для решения задачи.
Математическое описание
Предположим, что нам требуется решить задачу вычисления функции <math>y=f(x)</math>. Время вычисления зависит от числа операций, которое в свою очередь, зависит от некоторого числового параметра или набора параметров <math>n=(n_1, n_2, ...)</math>, характеризующих исходные данные <math>x</math>. Пусть время выражается зависимостью <math>t(n)</math>. Параметр <math>n</math> можно выбрать так, что функция <math>t(n)</math> будет расти с ростом <math>n</math>. Например, если <math>y=f(x)=f(x_1, x_2)</math> — решение системы линейных алгебраических уравнений с матрицей коэффициентов <math>x_1</math> и вектором свободных членов <math>x_2</math>, которое вычисляется одним из прямых методов, то в качестве <math>n</math> можно взять порядок системы. Если же система решается итерационным методом, то в качестве <math>n</math> можно взять пару — порядок системы и число итераций.
Допустим, что распределить вычисление функции <math>y=f(x)</math> равномерно между процессорами возможно так, что каждый из процессоров <math>p</math> будет работать время <math>t_p(n)=t(n)/p</math>. В реальной системе стоит также учитывать накладные расходы связанные с обменом информации между процессорами. Представим время потраченое на накладные расходы как <math>w_p(n)</math>, оно включает в себя собственно время необходимое для передачи данных, время на синхронизацию. Время решения задачи на системе из <math>p</math> процессоров обозначим как <math>T_p(n)</math>, тогда ускорение <math>a_p=a_p(n)</math> при решении задачи с параметром <math>n</math> можно выразить формулой:
- <math>a_p(n)=\frac{T_1(n)}{T_n(n)}=\frac{t(n)}{t_p(n)+w_p(n)}=\frac{1}{1+\tfrac{w_p(n)}{t_p(n)}}p=b_p(n) \cdot p.</math>
Формула имеет смысл только если <math>p<k(n)</math>, где <math>k(n)</math> — максимальное число процессоров, допускающее разумное разделение вычислительной работы при заданном размере задачи. Если <math>w_p(n)/t_p(n)<1</math>, то при изменении <math>p</math> от 1 до <math>k(n)</math> производительность растет не медленней, чем линейно с коэффициентом эффективности <math>b_p(n)>1/2</math>. Если же время, затрачиваемое на обмен, растет медленнее, чем время вычислений, то с ростом <math>n</math> коэффициент эффективности приближается к 1. Приведенная формула не учитывает многие дополнительные факторы, но она позволяет вести поиск эффективных алгоритмов для решения задач на многопроцессорных распределенных системах.
Напишите отзыв о статье "Макроконвейер"
Примечания
- ↑ 1 2 Словарь по кибернетике / Под редакцией академика В. С. Михалевича. — 2-е. — Киев: Главная редакция Украинской Советской Энциклопедии имени М. П. Бажана, 1989. — 751 с. — (С48). — 50 000 экз. — ISBN 5-88500-008-5.
Литература
- Глушков В. М., Погребинский С. Б., Рабинович З. Л. О развитии структур многопроцессорных вычислительных машин, интерпретирующих языки высокого уровня. — Управляющие системы и машины. 1978 г. № 6 — с.61-66.
- Глушков В. М. Об архитектуре высокопроизводительных машин. — Препринт Института Кибернетики № 78-65, Киев, 1978. — 41 с.
- Михалевич В. С., Капитонова Ю. В., Летичевский А. А., Молчанов И. Н., Погребинский С. Б. Организация вычислений в многопроцессорных вычислительных системах. Кибернетика. 1984 г. № 3 — с. 1-10
См. также
Отрывок, характеризующий Макроконвейер
– Прислуга к орудиям! – скомандовал офицер.И через минуту весело выбежали от костров артиллеристы и зарядили.
– Первое! – послышалась команда.
Бойко отскочил 1 й номер. Металлически, оглушая, зазвенело орудие, и через головы всех наших под горой, свистя, пролетела граната и, далеко не долетев до неприятеля, дымком показала место своего падения и лопнула.
Лица солдат и офицеров повеселели при этом звуке; все поднялись и занялись наблюдениями над видными, как на ладони, движениями внизу наших войск и впереди – движениями приближавшегося неприятеля. Солнце в ту же минуту совсем вышло из за туч, и этот красивый звук одинокого выстрела и блеск яркого солнца слились в одно бодрое и веселое впечатление.
Над мостом уже пролетели два неприятельские ядра, и на мосту была давка. В средине моста, слезши с лошади, прижатый своим толстым телом к перилам, стоял князь Несвицкий.
Он, смеючись, оглядывался назад на своего казака, который с двумя лошадьми в поводу стоял несколько шагов позади его.
Только что князь Несвицкий хотел двинуться вперед, как опять солдаты и повозки напирали на него и опять прижимали его к перилам, и ему ничего не оставалось, как улыбаться.
– Экой ты, братец, мой! – говорил казак фурштатскому солдату с повозкой, напиравшему на толпившуюся v самых колес и лошадей пехоту, – экой ты! Нет, чтобы подождать: видишь, генералу проехать.
Но фурштат, не обращая внимания на наименование генерала, кричал на солдат, запружавших ему дорогу: – Эй! землячки! держись влево, постой! – Но землячки, теснясь плечо с плечом, цепляясь штыками и не прерываясь, двигались по мосту одною сплошною массой. Поглядев за перила вниз, князь Несвицкий видел быстрые, шумные, невысокие волны Энса, которые, сливаясь, рябея и загибаясь около свай моста, перегоняли одна другую. Поглядев на мост, он видел столь же однообразные живые волны солдат, кутасы, кивера с чехлами, ранцы, штыки, длинные ружья и из под киверов лица с широкими скулами, ввалившимися щеками и беззаботно усталыми выражениями и движущиеся ноги по натасканной на доски моста липкой грязи. Иногда между однообразными волнами солдат, как взбрызг белой пены в волнах Энса, протискивался между солдатами офицер в плаще, с своею отличною от солдат физиономией; иногда, как щепка, вьющаяся по реке, уносился по мосту волнами пехоты пеший гусар, денщик или житель; иногда, как бревно, плывущее по реке, окруженная со всех сторон, проплывала по мосту ротная или офицерская, наложенная доверху и прикрытая кожами, повозка.
– Вишь, их, как плотину, прорвало, – безнадежно останавливаясь, говорил казак. – Много ль вас еще там?
– Мелион без одного! – подмигивая говорил близко проходивший в прорванной шинели веселый солдат и скрывался; за ним проходил другой, старый солдат.
– Как он (он – неприятель) таперича по мосту примется зажаривать, – говорил мрачно старый солдат, обращаясь к товарищу, – забудешь чесаться.
И солдат проходил. За ним другой солдат ехал на повозке.
– Куда, чорт, подвертки запихал? – говорил денщик, бегом следуя за повозкой и шаря в задке.
И этот проходил с повозкой. За этим шли веселые и, видимо, выпившие солдаты.
– Как он его, милый человек, полыхнет прикладом то в самые зубы… – радостно говорил один солдат в высоко подоткнутой шинели, широко размахивая рукой.
– То то оно, сладкая ветчина то. – отвечал другой с хохотом.
И они прошли, так что Несвицкий не узнал, кого ударили в зубы и к чему относилась ветчина.
– Эк торопятся, что он холодную пустил, так и думаешь, всех перебьют. – говорил унтер офицер сердито и укоризненно.
– Как оно пролетит мимо меня, дяденька, ядро то, – говорил, едва удерживаясь от смеха, с огромным ртом молодой солдат, – я так и обмер. Право, ей Богу, так испужался, беда! – говорил этот солдат, как будто хвастаясь тем, что он испугался. И этот проходил. За ним следовала повозка, непохожая на все проезжавшие до сих пор. Это был немецкий форшпан на паре, нагруженный, казалось, целым домом; за форшпаном, который вез немец, привязана была красивая, пестрая, с огромным вымем, корова. На перинах сидела женщина с грудным ребенком, старуха и молодая, багроворумяная, здоровая девушка немка. Видно, по особому разрешению были пропущены эти выселявшиеся жители. Глаза всех солдат обратились на женщин, и, пока проезжала повозка, двигаясь шаг за шагом, и, все замечания солдат относились только к двум женщинам. На всех лицах была почти одна и та же улыбка непристойных мыслей об этой женщине.
