Процесс параллельной обработки данных. Последовательная и параллельная обработка информации
Таким образом, основные признаки, характеризующие супер-ЭВМ , следующие:
- самая высокая производительность;
- самый современный технологический уровень (например, GaAs -технология);
- специфические архитектурные решения, направленные на повышение быстродействия (например, наличие операций над векторами);
- цена, обычно свыше 1-2 млн. долларов.
Какой из факторов является решающим в достижении современных фантастических показателей производительности? Обратимся к историческим фактам. На одном из самых первых компьютеров EDSAC (1949 г.), имевшем время такта 2 мкс, можно было выполнить в среднем 100 арифметических операций в секунду. А пиковая производительность суперкомпьютера CRAY C90 с временем такта порядка 4 нс - около 1 миллиарда арифметических операций в секунду. Таким образом, производительность компьютеров за этот период возросла примерно в 10 миллионов раз, а время такта уменьшилось лишь в 500 раз. Следовательно, увеличение производительности происходило и за счет других факторов, важнейшим среди которых является использование новых архитектурных решений, в частности - принципа параллельной обработки данных .
Имеет две разновидности: конвейерность и параллельность.
Идея конвейерной обработки заключается в выделении отдельных этапов выполнения общей операции , причем так, чтобы каждый этап, выполнив свою работу, передавал бы результат следующему, одновременно принимая новую порцию входных данных. Выигрыш в скорости обработки данных получается за счет совмещения прежде разнесенных во времени операций.
Параллельная обработка данных предполагает наличие нескольких функционально независимых устройств.
Закон Амдала
Закон Амдала
S<= 1/
где S - ускорение, f - доля операций, которые нужно выполнить последовательно, p - число процессоров.
Следствие из закона Амдала : для того чтобы ускорить выполнение программы в q раз, необходимо ускорить не менее чем в q раз и не менее чем (1-1/q) -ую часть программы. Следовательно, если нужно ускорить программу в 100 раз по сравнению с ее последовательным вариантом, то необходимо получить не меньшее ускорение на не менее чем 99,99 % кода!
История появления параллелизма в архитектуре ЭВМ
Все современные процессоры используют тот или иной вид
Параллельная и конвейерная обработка
В параллельной обработке данных, воплощается идея одновременного выполнения нескольких действий, таких как конвейерность и параллельность .
Параллельная обработка
При выполнении устройством одной операции за единицу времени, можно сказать, что тысячу операций устройство выполнит за тысячу единиц. Если предположить, что есть пять независимых устройств, работающих одновременно, то ту же тысячу операций такая система устройств может выполнить уже за двести единиц времени. По аналогии система из N устройств ту же работу выполнит за 1000/N единиц времени. К реальной жизни это также применимо, например:
огород может быть вскопан одним солдатом за 10 часов, а рота солдат количеством 50 человек с такими же способностями при одновременной работе выкопают его уже за 12 минут — действие принципа параллельности в действии .
Самарский А.А., выполнявший в начале 50-х годов расчеты для моделирования ядерных взрывов был пионером в параллельной обработке потоков данных. Самарский интересным способом рассчитал эволюцию взрывной волны — он посадил несколько десятков человек с арифмометрами за столы, заставив их передавать данные друг другу просто на словах и откладывать необходимые цифры на арифмометрах. Можно сказать, что это
и была первая параллельная система. Не смотря на то, что расчеты водородной бомбы были мастерски проведены, их точность была довольно низка, потому что используемая сетка имела мало узлов, а время счета было слишком большим.Конвейерная обработка
Для сложения двух вещественных чисел, представленных в форме с плавающей запятой, необходимо проделать великое множество мелких операций — сравнить порядки, выровнять порядки, сложить мантиссы, нормализовать и т.п. Все эти «микрооперации» для каждой пары аргументов процессоры первых компьютеров осуществляли последовательно одну за другой, до тех пор, пока не доходили до окончательного результата, и лишь затем обрабатывалась следующая пара
слагаемых.Суть конвейерной обработки состоит в выделении отдельных этапов выполнения общей операции. Каждый этап, выполнив свою работу, передавал бы результат следующему, одновременно принимая новую порцию данных. Совмещение прежде разрозненных во времени операций определенно положительно влияет на скорость обработки. Например, в операции можно выделить пять микроопераций, каждая из которых выполняется за одну единицу времени.
Если есть одно неделимое последовательное устройство, то 100 пар аргументов оно обрабатывает за 500 единиц. Если каждую микрооперацию выделить в отдельный этап (или ступень) конвейерного устройства, то на пятой единице времени на разной стадии обработки такого устройства будут находиться первые пять пар аргументов, а весь набор из ста пар будет обработан за 104 (5+99) единицы времени — ускорение по сравнению с последовательным устройством почти в пять раз (по числу ступеней конвейера).Казалось бы, конвейерную обработку можно с успехом заменить обычным параллелизмом, достаточно просто продублировать основное устройство столько раз, сколько ступеней конвейера предполагается выделить. В самом деле, 5 устройств за 100 единиц времени обрабатывают 100 пар аргументов, что быстрее времени работы конвейерного устройства. Если увеличить в пять раз число устройств, объем аппаратуры и ее стоимость значительно возрастут. Например, рассмотрим ситуацию, когда убирается конвейер на автозаводе, при этом темпы выпуска автомобилей необходимо сохранить, соответственно потребуется тысяча бригад, каждая из которых может от начала до конца собрать автомобиль, проделав сотни различных операций, причем за довольно короткое время.
Стоимость автомобиля будет колоссальной. Поэтому и возникла конвейерная обработка .
Современные параллельные системы
В настоящее время выделяют четыре направления в развитии высокопроизводительной вычислительной техники.
Векторно-конвейерные компьютеры
Особенности таких машин заключаются в наборе векторных команд и конвейерных функциональных устройствах. В отличие от традиционного подхода, векторные команды способны оперировать целыми массивами независимых данных, а значит появляется возможность эффективно загружать доступные конвейеры, т.е. команда вида А=В+С может означать не сложение двух чисел, а двух массивов. Характерный представитель данного направления — семейство векторно-конвейерных компьютеров CRAY.
Массивно-параллельные компьютеры с распределенной памятью.
Построение компьютеров этого класса отличается простой идеей: каждый серийный микропроцессор, оборудуются своей локальной памятью, затем соединяются посредством некоторой коммуникативной среды. У такой архитектуры имеется масса достоинств: для увеличения производительности достаточно увеличить количество процессоров, оптимальная конфигурация легко подбирается в случае, если известна требуемая вычислительная мощность.
Однако, существует значительный минус, превосходящий многие плюсы. В данных компьютерах межпроцессорное взаимодействие идет намного медленнее, чем происходит локальная обработка данных самими процессорами. В связи с этим, очень сложно написать эффективную программу для таких компьютеров, для некоторых алгоритмов иногда просто невозможно. Примеры таких компьютеров: Intel Paragon, IBM SP1, Parsytec, в некоторой степени IBM SP2 и CRAY T3D/T3E, хотя влияние указанного минуса в этих компьютерах значительно меньше. Сети компьютеров, которые все чаще рассматривают как достаточно дешевую альтернативу крайне дорогим компьютерам, так же можно отнести к этому же классу.
Параллельные компьютеры с общей памятью
Вся оперативная память данных компьютеров разделяется несколькими одинаковыми процессорами. Проблемы предыдущего класса решены, но добавились новые — нельзя по технически причинам сделать большим число процессоров, которые имели бы доступ к общей памяти. Примерами данного направления многие многопроцессорные SMP-компьютеры или, например, отдельные узлы компьютеров HP Exemplar и Sun StarFire.
Комбинированные системы
Последнее направление скорее не самостоятельное, а просто комбинация предыдущих трех. Сформируем вычислительный узел из нескольких процессоров (традиционных или векторно-конвейерных) и общей для них памяти. При нехватке вычислительной мощности, можно объединить несколько узлов высокоскоростными каналами. Подобная архитектура называется кластерной. По данному принципу построены Sun StarFire, NEC SX-5, CRAY SV1, HP Exemplar, последние модели IBM SP2 и другие.
Данное направление является в настоящий момент наиболее перспективным для конструирования компьютеров с рекордными показателями производительности .
Уровни параллелизма
В зависимости от того, на каком уровне должен обеспечиваться параллелизм, используются те или иные методы и средства реализации. Различают следующие уровни параллелизма.
Микроуровень . Выполнение команды разделено на фазы, а фазы нескольких соседних команд могут быть перекрыты за счет конвейеризации. Достичь данный уровень возможно на ВС с одним процессором.
Уровень потоков . Задачи разбиваются на части, которые могут выполняться параллельно (потоки). Данный уровень достигается на параллельных ВС.
Уровень команд . Несколько команд выполняются параллельно, в процессоре размещаются сразу несколько конвейеров. Характерен для суперскалярных процессоров.
Уровень заданий . Независимые задания одновременно выполняются на разных процессорах, взаимодействие друг с другом практически не происходит. Уровень характерен для многопроцессорных и многомашинных ВС.
Понятие уровня параллелизма тесно связано с понятием гранулярности. Гранулярность — мера отношения объема вычислений, выполненных в параллельной задаче, к объему коммуникаций (для обмена сообщениями). Степень гранулярности варьируется от мелкозернистой до крупнозернистой. Закон Амдала ориентирован на крупнозернистый
параллелизм.Крупнозернистый параллелизм заключается в том, что каждое параллельное вычисление достаточно независимо от остальных, к тому же отдельные вычисления требуют относительно редкий обмен информацией между собой. Единицами распараллеливания являются большие и независимые программы, включающие тысячи команд. Операционная система обеспечивает данный уровень параллелизма.
Для эффективного параллельного исполнения необходимо балансировать между степенью гранулярности программ и величиной коммуникационной задержки, которая возникает между разными гранулами. Для минимальной коммуникационной задержки лучше всего подходит мелкоструктурное разбиение программы. В таком случае действует параллелизм данных. Если коммуникационная задержка большая, то лучше использовать крупнозернистое разбиение программ .
Литература
- Баденко В.Л. Высокопроизводительные вычисления. Учебное пособие. - СПб.: Изд-во Политехн. ун-та, 2010. — 180 с.
- Барский А.Б. Параллельные информационные технологии: Учебное пособие/А.Б. Барский.-М.: Интернет-университет информационных технологий; БИНОМ. Лаборатория знаний, 2007.-503 с.: ил.,таб.-(серия «Основы информационных технологий»)- с.20-28, с.56-58.
- Корнеев В.В. Вычислительные системы.-М.:Гелиос APB, 2004.-512с., ил.- с. 34-46
- Лацис А.О. Параллельная обработка данных. М.: Академия, 2010. - 336 с.
- Цилькер Б.Я., Орлов С.А. Организация ЭВМ и систем. Учебник для вузов. - СПб.: Питер, 2004. - 668 с.
Сообщения
Сообщения
Пути повышения производительности ВС заложены в ее архитектуре. С одной стороны это совокупность процессоров, блоков памяти, устройств ввода/вывода ну и конечно способов их соединения, т.е. коммуникационной среды. С другой стороны, это собственно действия ВС по решению некоторой задачи, а это операции над командами и данными. Вот собственно и вся основная база для проведения параллельной обработки. Параллельная обработка, воплощая идею одновременного выполнения нескольких действий, имеет несколько разновидностей: суперскалярность, конвейеризация, SIMD – расширения, Hyper Threading , многоядерность. В основном эти виды параллельной обработки интуитивно понятны, поэтому сделаем лишь небольшие пояснения. Если некое устройство выполняет одну операцию за единицу времени, то тысячу операций оно выполнит за тысячу единиц. Если предположить, что есть, пять таких же независимых устройств, способных работать одновременно, то ту же тысячу операций система из пяти устройств может выполнить уже не за тысячу, а за двести единиц времени. Аналогично система из N устройств ту же работу выполнит за 1000/N единиц времени. Подобные аналогии можно найти и в жизни: если один солдат вскопает огород за 10 часов, то рота солдат из пятидесяти человек с такими же способностями, работая одновременно, справятся с той же работой за 12 минут (параллельная обработка данных), да еще и с песнями (параллельная обработка команд).
Конвейерная обработка . Что необходимо для сложения двух вещественных чисел, представленных в форме с плавающей запятой? Целое множество мелких операций таких, как сравнение порядков, выравнивание порядков, сложение мантисс, нормализация и т.п. Процессоры первых компьютеров выполняли все эти "микрооперации" для каждой пары аргументов последовательно одна за одной до тех пор, пока не доходили до окончательного результата, и лишь после этого переходили к обработке следующей пары слагаемых. Идея конвейерной обработки заключается в выделении отдельных этапов выполнения общей операции, причем каждый этап, выполнив свою работу, передавал бы результат следующему, одновременно принимая новую порцию входных данных. Получаем очевидный выигрыш в скорости обработки за счет совмещения прежде разнесенных во времени операций.
Суперскалярность. Как и в предыдущем примере, только при построении конвейера используют несколько программно-аппаратных реализаций функциональных устройств, например два или три АЛУ, три или четыре устройства выборки.
Hyper Threading . Перспективное направление развитие современных микропроцессоров, основанное на многонитевой архитектуре. Основное препятствие на пути повышения производительности за счет увеличения функциональных устройств – это организация эффективной загрузки этих устройств. Если сегодняшние программные коды не в состоянии загрузить работой все функциональные устройства, то можно разрешить процессору выполнять более чем одну задачу (нить), чтобы дополнительные нити загрузили – таки все ФИУ (очень похоже на многозадачность).
Многоядерность . Можно, конечно, реализовать мультипроцессирование на уровне микросхем, т.е. разместить на одном кристалле несколько процессоров (Power 4). Но если взять микропроцессор вместе с памятью как ядра системы, то несколько таких ядер на одном кристалле создадут многоядерную структуру. При этом в кристалле интегрируются функции (например, интерфейсы сетевых и телекоммуникационных систем) для выполнения которых обычно используются наборы микросхем (процессоры Motorola MPC8260, Power 4).
Реализация высокопроизводительной вычислительной техники в настоящее время идёт по четырем основным направлениям.
1. Векторно-конвейерные компьютеры . Конвейерные функциональные устройства и набор векторных команд - это две особенности таких машин. В отличие от традиционного подхода, векторные команды оперируют целыми массивами независимых данных, что позволяет эффективно загружать доступные конвейеры, т.е. команда вида A=B+C может означать сложение двух массивов, а не двух чисел. Характерным представителем данного направления является семейство векторно-конвейерных компьютеров CRAY куда входят, например, CRAY EL, CRAY J90, CRAY T90 (в марте 2000 года американская компания TERA перекупила подразделение CRAY у компании Silicon Graphics, Inc.).
2. Массивно-параллельные компьютеры с распределенной памятью. Идея построения компьютеров этого класса тривиальна: возьмем серийные микропроцессоры, снабдим каждый своей локальной памятью, соединим посредством некоторой коммуникационной среды - вот и все. Достоинств у такой архитектуры масса: если нужна высокая производительность, то можно добавить еще процессоров, если ограничены финансы или заранее известна требуемая вычислительная мощность, то легко подобрать оптимальную конфигурацию и т.п.
Однако есть и решающий "минус", сводящий многие "плюсы" на нет. Дело в том, что самостоятельным, а скорее представляет собой комбинации предыдущих трех. Из нескольких процессоров (традиционных или векторно-конвейерных) и общей для них памяти сформируем вычислительный узел. Если полученной вычислительной мощности не достаточно, то объединим несколько узлов высокоскоростными каналами. Подобную архитектуру называют кластерной SV1 , HP Exemplar , Sun StarFire , NEC SX-5 , последние модели IBM SP2
3. Параллельные компьютеры с общей памятью . Вся оперативная память таких компьютеров разделяется несколькими одинаковыми процессорами. Это снимает проблемы предыдущего класса, но добавляет новые - число процессоров, имеющих доступ к общей памяти, по чисто техническим причинам нельзя сделать большим. В данное направление входят многие современные многопроцессорные SMP-компьютеры или, например, отдельные узлы компьютеров HP Exemplar и Sun StarFire .
4. Кластерные системы. Последнее направление, строго говоря, не является самостоятельным, а скорее представляет собой комбинации предыдущих трех. Из нескольких процессоров (традиционных или векторно-конвейерных) и общей для них памяти сформируем вычислительный узел. Если полученной вычислительной мощности не достаточно, то объединим несколько узлов высокоскоростными каналами. Подобную архитектуру называют кластерной , и по такому принципу построены CRAY SV1 , HP Exemplar , Sun StarFire , NEC SX-5 , последние модели IBM SP2 и другие. Именно это направление является в настоящее время наиболее перспективным для конструирования компьютеров с рекордными показателями производительности.
Параллельная обработка
Параллельная обработка
Параллельная обработка - модель выполнения прикладного процесса одновременно группой процессоров. Различают три способа реализация параллелизма:
-1- способ SIMD работы с одним потоком команд и несколькими потоками данных, при котором все процессоры, работающие по одной программе, обрабатывают собственные массивы данных под управлением ведущего процессора;
-2- способ MIMD работы с несколькими потоками команд и несколькими потоками данных, при котором процессоры работают по своим программам независимо друг от друга, лишь эпизодически связываясь друг с другом;
-3- способ MISD работы с несколькими потоками команд и одним потоком данных.
По-английски: Parallel processing
Финансовый словарь Финам .
Смотреть что такое "Параллельная обработка" в других словарях:
Параллельная обработка - Один из видов обработки информации, когда несколько операций могут выполняться одновременно. В отличие от осознанной обработки, которая обычно выполняется последовательно, этот вид обработки происходит без осознанных усилий. Например, читая эти… …
- (parallel processing) Метод работы на компьютере, при котором две или несколько частей программы выполняются не последовательно, а параллельно. Строго говоря, применение данного метода возможно только на компьютерах, обладающих двумя и более… … Словарь бизнес-терминов
параллельная обработка - — Тематики электросвязь, основные понятия EN parallel processing …
параллельная обработка - lygiagretusis apdorojimas statusas T sritis automatika atitikmenys: angl. parallel processing vok. Parallelverarbeitung rus. параллельная обработка, f pranc. traitement en parallèle, m … Automatikos terminų žodynas
параллельная обработка информации - модель обработки информации в мозге головном, согласно коей информация проходит ряд преобразований в определенных «функциональных блоках» мозга так, что в каждый момент времени ее обработка ведется одновременно (параллельно) в нескольких… … Большая психологическая энциклопедия
ПАРАЛЛЕЛЬНАЯ ОБРАБОТКА ИНФОРМАЦИИ - См. обработка информации, параллельная …
Способ параллельной обработки данных большим числом процессоров, реализующий способ организации параллелизма MIMD. По английски: Massively Parallel Processing Синонимы английские: MPP См. также: Параллельная обработка Финансовый словарь Финам … Финансовый словарь
ОБРАБОТКА, ПАРАЛЛЕЛЬНАЯ - Обработка информации, при которой более чем одна последовательность операций по обработке проводятся одновременно, или параллельно. Обработка может включать чрезвычайно низкий уровень, несимволические компоненты, такие, которые используются в… … Толковый словарь по психологии
параллельная конвейерная обработка - lygiagretusis konvejerinis apdorojimas statusas T sritis radioelektronika atitikmenys: angl. parallel pipelining vok. Parallel Pipelineverarbeitung, f rus. параллельная конвейерная обработка, f pranc. traitement de pipeline parallèle, m … Radioelektronikos terminų žodynas
одновременная обработка - параллельная обработка — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Тематики информационные технологии в целом Синонимы параллельная обработка EN simultaneous processing … Справочник технического переводчика
Книги
- Параллельная обработка данных
- Параллельная обработка данных , А. О. Лацис. В учебном пособии дан углубленный систематический обзор технологий параллельной обработки данных. Основное внимание уделено традиционным программным технологиям параллельного программирования…
1.2 Параллельная обработка данных
1.2.1 Принципиальная возможность параллельной обработки
Практически все разработанные к настоящему времени алгоритмы являются последовательными. Например, при вычислении выражения a + b × c , сначала необходимо выполнить умножение и только потом выполнить сложение. Если в электронно-вычислительных машин присутствуют узлы сложения и умножения, которые могут работать одновременно, то в данном случае узел сложения будет простаивать в ожидании завершения работы узла умножения. Можно доказать утверждение, состоящее в том, что возможно построить машину, которая заданный алгоритм будет обрабатывать параллельно.
Можно построить m процессоров, которые при одновременной работе выдают нужный результат за один-единственный такт работы вычислителя.
Такие "многопроцессорные" машины теоретически можно построить для каждого конкретного алгоритма и, казалось бы, "обойти" последовательный характер алгоритмов. Однако не все так просто – конкретных алгоритмов бесконечно много, поэтому развитые выше абстрактные рассуждения имеют не столь прямое отношение к практической значимости. Их развитие убедило в самой возможности распараллеливания, явилось основой концепции неограниченного параллелизма, дало возможность рассматривать с общих позиций реализацию так называемых вычислительных сред – многопроцессорных систем, динамически настраиваемых под конкретный алгоритм.
1.2.2 Абстрактные модели параллельных вычислений
Модель параллельных вычислений обеспечивает высокоуровневый подход к определению характеристик и сравнению времени выполнения различных программ, при этом абстрагируются от аппаратного обеспечения и деталей выполнения. Первой важной моделью параллельных вычислений явилась машина с параллельным случайным доступом (PRAM – Parallel Random Access Machine), которая обеспечивает абстракцию машины с разделяемой памятью (PRAM является расширением модели последовательной машины с произвольным доступом RAM – Random Access Machine). Модель BSP (Bulk Synchronous Parallel, массовая синхронная параллельная) объединяет абстракции как разделенной, так и распределенной памяти. Считается, что все процессоры выполняют команды синхронно; в случае выполнения одной и той же команды PRAM является абстрактной SIMD-машиной, (SIMD – Single Instruction stream/Multiple Data stream – одиночный поток команд наряду со множественным потоком данных), однако процессоры могут выполнять и различные команды. Основными командами являются считывание из памяти, запись в память и обычные логические и арифметические операции.
Модель PRAM идеализирована в том смысле, что каждый процессор в любой момент времени может иметь доступ к любой ячейке памяти (Операции записи, выполняемые одним процессором, видны всем остальным процессорам в том порядке, в каком они выполнялись, но операции записи, выполняемые разными процессорами, могут быть видны в произвольном порядке). Например, каждый процессор в PRAM может считывать данные из ячейки памяти или записывать данные в эту же ячейку. На реальных параллельных машинах такого, конечно, не бывает, поскольку модули памяти на физическом уровне упорядочивают доступ к одной и той же ячейке памяти. Более того, время доступа к памяти на реальных машинах неодинаково из-за наличия кэшей и возможной иерархической организации модулей памяти.
Базовая модель PRAM поддерживает конкурентные (в данном контексте параллельные) считывание и запись. Известны подмодели PRAM, учитывающие правила, позволяющие избежать конфликтных ситуаций при одновременном обращении нескольких процессоров к общей памяти.
Моделировать схемы из функциональных элементов с помощью параллельных машин с произвольным доступом (PRAM) позволяет теорема Брента. В качестве функциональных элементов могут выступать как 4 основных (осуществляющих логические операции NOT, AND, OR, XOR – отрицание, логическое И, логическое ИЛИ и исключающее ИЛИ соответственно), более сложные NAND и NOR (И-НЕ и ИЛИ-НЕ), так и любой сложности.
В дальнейшем предполагается, что задержка (т.е. время срабатывания – время, через которое предусмотренные значения сигналов появляются на выходе элемента после установления значений на входах) одинакова для всех функциональных элементов.
Рассматривается схема из функциональных элементов, соединенных без образования циклов (предполагаем, что функциональные элементы имеют любое количество входов, но ровно один выход – элемент с несколькими выходами можно заменить несколькими элементами с единственным выходом). Число входов определяет входную степень элемента, а число входов, к которым подключен выход элемента – его выходной степенью. Обычно предполагается, что входные степени всех используемых элементов ограничены сверху, выходные же степени могут быть любыми. Под размером схемы понимается количество элементов в ней, наибольшее число элементов на путях от входов схемы к выходу элемента называется глубиной этого элемента (глубина схемы равна наибольшей из глубин составляющих ее элементов).
Рисунок 1. Моделирование схемы размера 15, глубины 5 с двумя процессорами с помощью параллельной машины с произвольным доступом (PRAM – машина)
На рисунке 1 приведен результат моделирования схемы размером (общее количество процессоров) n=15 при глубине схемы (максимальное число элементов на каждом из уровней глубины) d=5 с числом процессоров p=2 (одновременно моделируемые элементы объединены в группы прямоугольными областями, причем для каждой группы указан шаг, на котором моделируются ее элементы; моделирование происходит последовательно сверху вниз в порядке возрастания глубины, на каждой глубине по р штук за раз). Согласно теоремы Брента моделирование такой схемы займет не более ceil(15/2+1)=9 шагов.