Разработка имитационной модели мультипроцессорной системы с локальной кэш-памятью и анализ основных результатов моделирования тема диссертации и автореферата по ВАК РФ 01.01.10, кандидат физико-математических наук Бекич, Зоран

• Бекич, Зоран
• кандидат физико-математических наук
• 1984

Оглавление диссертации кандидат физико-математических наук Бекич, Зоран

Глава 1. Введение.1

1.1 Идея параллелизма в работе вычислительных систем .1

1.2 Параллельные вычислительные системы и их основная классификация .1

Глава 2. Постановка задачи и ее методологическая разработка .2

2.1 Проблема деградации производительности мультипроцессорных систем .2

2.2 Архитектура оперативной памяти в мультипроцессорных системах .2

2.3 Основные параметры архитектуры мультипроцессорных систем с локальной кэш-памятью .2

2.4 Окончательное определение задачи и выбор метода решения .2

2.5 Поведение программ и возможности его моделирования . 2

2.6 Структура расходов на обмены с памятью и мера ' производительности .2

Глава 3. Описание имитационной модели мультипроцессорной системы с локальной кэш-памятью .3

3.1 Общая структура системы моделирования .3

3.2 Фиксированные параметры архитектуры и общие предположения в модели МПС с локальной кэш-памятью .3

3.3 Моделирование поведения программ .3

3.4 Входные параметры модели и блок-схемы программ моделирования . .3

3.5 Выходные результаты модели и форма их выдачи .3

3.6 0 верификации модели .3

Глава 4. Анализ основных результатов моделирования .4

4.1 Вводные замечаний .4

4.2 Сравнение результатов моделирования по группам .4

4.3 Анализ влияния поведения программ на эффективную производительность МПС с локальной кэш-памятью .4

Введение диссертации (часть автореферата) на тему «Разработка имитационной модели мультипроцессорной системы с локальной кэш-памятью и анализ основных результатов моделирования»

1.1 Идея параллелизма в работе вычислительных систем.

Многообразны причины и пути эволюции вычислительных систем, развития их архитектуры, начиная от классической концепции фон Неймана до мультипроцессорных вычислительных систем наших дней и кончая параллельными и- распределенными архитектурами завтрашнего дня.

Говоря о причинах, движущих силах этого бурного, незатухающего процесса развития, протекающего со скоростью, невиданной в области технических знаний человека, можно указать как на внешние, так и на внутренние его источники.

Первый, внешний, и наверное, все-таки, главный источник этого непрерывного развития - постоянная потребность человека в вычислительных системах, более мощных, чем существующие в данный момент Тем и примечателен процесс применения ЭВМ человеком, что на каждом его этапе не только удовлетворяются существуюдие погребности, но"и |порожда- ] ются]новые, более комплексные и сложные. Таким образом, задачи и цели, которые ставил человек, и которые решал и достигал при помощи ЭВМ, становились и становятся все более сложными. Усложнение задач необходимо выдвигает требование развития и совершенствования' инструментов, которыми они решаются.

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

Сложность вычислительных систем и необходимость их эффективного использования привели к тому, что вычислительные системы, являясь инструментом исследования и познания человека, очень быстро стали и объектом этого исследования и познания. Результаты этого исследования, необходимость которого порождена бурным процессом развития ЭВМ, несомненно становятся одним из источников дальнейшего продолжения этого процесса.

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

Существуют, однако, некоторые идеи и принципы, присутствие и влияние которых, можно заметить во всех переломных моментах развития вычислительной техники. И таким идеям, безусловно, можно отнести идею параллелизма в работе вычислительных систем.

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

Идея параллелизма в работе аппаратуры ЭВМ присутствует уже в первых вычислительных машинах, которые параллельно обрабатывали и передавали все разряды машинного слова. Настоящее применение идеи параллелизма, однако, наблюдается тольно в пятидесятых годах, когда впервые реализуется совмещение во времени процессов ввода-вывода и вычислений за счет внедрения возможности непосредственного обмена между внешними запоминающими устройствами и памятью. Этим сначала освобождается во время ввода-вывода арифметическое устройство, а внедрением автоматического канала в вода-вывода - и устройство управления. Таким образом, отдельные части фон-Неймановской вычислительной машины стали работать независимо, что привело к тому что в определенных промежутках времени они работали параллельно. Появление все новых задач, которые решались1 на ЭВМ, требовало все ! большей скорости работы аппаратуры. Однако, эта скорость всегда ограничена общим уровнем развития элементной базы ЭВМ, а- в конечно счете, и скоростью света, равной 30 см/нсек.

Поэтому, увеличение возможностей аппаратуры ЭВМ нередко приходится: искать в области улучшения архитектуры вычислительных систем. Именно на этом пути появились сначала многомашинные, а потом и мультипроцессорные /многопроцессорные/ системы. Их основная внешняя отличительная характеристика - дублирование основных компонент фон-Неймановской вычислитильной машины /процессоров, модулей основной памяти, каналов в вода-вывода/, которые работают параллельн во времени, но под более или менее сильным общим управлением.

Отражением идеи параллелизма в работе ЭВМ является и применение совмещения командой опережающий.просмотр команд и данных, которые • успешно применяются и в однопроцессорных, ч. и в мультипроцессорных вычислительных системах. Речь очевидно идет о применении идеи парал .лелизма на более низком уровне рассмотрения архитектуры' ЭВМ.

Идеу параллелизма проявились и проявляются не только в работе аппаратуры вычислительных систем, но и при создании как системного, так и прикладного математического обеспечения. Первым проявлением этой идеи явилась программная реализация режима мультипрограммирования, при котором несколько различных программ одновременно ре-шяются в ЭВМ, так что каждая из них в какой-то момент времени использует какое то подмножество системных ресурсов. -Первоначальным

1-4 | преимуществом режима мультипрограммирования явилось повышение эффективности использования ресурсов вычислительной системы и повышение ее общей пропускной способности. Однако, появление мультипроцессорных систем привело к тому, что в режиме мультипрограммирования стало возможным ускорение и каждого конкретного задания, за счет разбиения его на параллельные независимые части, которые могут параллельно во времени выполняться в вычислительной системе. Эта возможность является весьма важным результатом применения идей параллелизма в работе ЭВМ.

1!.2 Параллельные вычислительные системы и их основная классификация.

Идеи параллелизма настолько распространены во всех вычислительных системах, что к изучению всего разнообразия вычислительных систем, как и к их классификации, можно подойти с точки зрения параллельности их работы. Более того, при таком подходе можно, и даже необходимо, рассматривать различные признаки параллельности в работе.

Так по типу потока данных можно различать системы с одиночным /ОД/ и множественным /МД/ потоком данных. По типу потока команд - с одиночным /ОК/ и множественным /ПК/ потоком команд.

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

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

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

Однородные мультипроцессорные вычислительные системы /МПС/ являются объектом рассмотрения данной диссертационной работы.

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

ГЛАВА 2.

Постановка задами и ее методологическая разработка.

2.1 Проблема деградации производительности мультипроцессорных систем.

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

На сегодняшний день не существует общеприменимого соотношения между номинальной и эффективной производительностью мультипроцессорных систем1.- В связи с тем, что мультипроцессорные системы очень разнообразны по своей архитектуре и по области своего применения, а значит и,по задачам, которые с их помощю решаются, : ^ можно усомниться и в самой возможности определения такого универсального соотношения.

Если говорить о некоторых известных результатах анализа работы реальных мультипроцессорных систем, то можно сказать, что случаи когда эффективная производительность близка к номинальной довольно редкие, и в то же время, гипотеза о логарифмической зависимости между номинальной и эффективной производительностью, известная как гипотеза Минского /[120]/, является слишком заниженной.

Единственный правильный на сегодняшний день подход к вопросу оценки эффективной производительности пультипроцессорных ситем, есть индивидуальный подход к каждой конкретной мультипроцессорной архитектуре.

Если попробоват ь систематизировать! источники специфических накладных расходов, которые приводят к деградации производительности мультипроцессорных систем! то их можно разбить на 4 класса /11721/:

1. накладные расходы управляющих программ, которые обеспечивают функционирование МПС как единного целого,

2. блокировки процессоров по доступу к общесистемным таблицам математического обеспечения, которые обеспечивают координированное управление, Р

Работа прик ладной программы В

Блокировка по одновременным обращениям к общим ресурсам

Работа управляющих программ МПС

Нет задании

Блокировка по общесистемным таблицам ---гО

Модули основной памяти

Внешн ие эапоминающ ус- ва

Общее математ. обеспечен

Система связи ком понент МПС

Рис. 1. Состояния МПС с точки зрения возникновения накладных расходов. 3. блокировки процессоров из-за одновременного обращения к общесистемным ресурсам, прежде всего к оперативной памяти /модулю оперативной памяти/,

4. простои процессоров из-за отсутсвия заданий.

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

Если говорить о понижении накладных расходов, относящихся к первым двум классам, 'то в 1172] предлагаются следующие возможности для достижения этой цели:

1. Повышение эффективности выполнения управляющих программ посредством: а/ ограничения использования блокировок процессоров управляющей программой, б/ уменьшения времени выполнения критических секций, т.е. оптимизацией управляющих программ, в/ разбиением управляющих программ на несколько независимых частей, которые выполняются параллельно, без взаимных блокировок, г/ разработкой специальной аппаратуры для выполнения управляющих программ МПС,

2. Повышение индивидуальной эффективности процессоров, т.е. уменьшение времени выполнения системных программ по отношению к времени выполнения прикладных программ.

Простои процессоров из-за отсутствия заданий на входе МПС являются важной проблемой, которая, однако, существенно отличается от остальных перечисленных тем, что она никак не связана с внутреней архитектурой МПС. Третий класс источников накладных расходов является довольно обширным, но во всей своей совокупности не является спецификой только мультипроцессорных систем. Очереди на устройства ввода-вывода, например, характерны и для классических однопроцессорных систем с режимом мультипрограммирования.

Одновременные обращения в оперативную память, однако, стали качественно новой проблемой для мультипроциссорных ситем. Исследование их характера и способов уменьшения их числа является глобальной темой данной диссертации.

2.2 Архитектура оперативной памяти в мультипроцессорных системах.

Значительное увеличение вычислительной мощности, как следствие параллельной активности нескольких процессоров - желаемая, и, вообще'г то, достижимая ]цель разработчиков МПС. Такой скачок вычислительной мощности очевидно поставил новые требования к архитектуре и организации памяти в таких вычислительных системах.

Неудивительно поэтому, что в мультипроцессорных системах очень интенсивно применяются методы организации памяти, которые 'использовались еще в однопроцессорных системах и которые обеспечивают рост возможностей памяти.

К числу таких методов относится концепция многоуровневой памяти, как средства достижения компромисса между практически неограниченными I потребностями процессоров в как можно более быстрой памяти и стоимостью вычислительной системы.

Практически всегда используется и метод разбиения основной памяти на независимые модули, чем достигается возможность одновременного удовлетворения нескольких запросов в память, при услов.ии, что они обращены к различным ее модулям.

Связанным с тольно что упомянутым методом, является и метод расслоения памяти, т.е. распределения последовательных /по адресам/ слов по различным модулям основной памяти. Применение расслоения /возможно в немного видоизмененой форме/ является общепринятым и в мультипроцессорных системах.

Концепция математического, или даже физического разделения области данных от области хранения команд так же может быть с успехом использована в МПС.

Рис. 2. Простейшая архитектура МПС

Внедрение кэш-памяти в архитектуру памяти МПС преследует те же цели, что и внедрение такой памяти в классических вычислительных системах. Характеристиками кэш-памяти являются ее большая, по сравнению с основной памятью, скорость и соответственно большая стоимость, а следовательно, в принципе относительно небольшой размер. Общепринятым назначением нэш-памяти является хранение наиболее часто используемых участков основной памяти /данных и-или команд/. При этом, за счет большей скорости кэшпамяти и при удачном определении множества данных, которые хранятся в ней, существенно может уменьшиться общее время, затрачиваемое на обмены с памятью.'

Вводом кэш-памяти исключительно1 в указанной функции мы переходим от простейшей МПС к мультипроцессорной архитектуре с общей кэш-памят ью:

Рис. 3. Мультипроцессорная система с общей кэш-памятью Термин "общая" появляется в данном названии в связи с тем, что кэш-память, также как и модули основной памяти, остается общим, разделяемым ресурсом всех процессоров. Каждая кэш-память обычно связывается только с определенным модулем основной памяти, хотя можно было бы рассматривать архитектуру памяти и без этого огранич ения.

Возвращаясь теперь к проблеме, которой мы закончили' предыдущий раздел, а именно к проблеме одновременых обращений к модулям основной памяти, как источнику накладных расходов в работе МПС, мы должны заметить, что ни одна из архитектурных возможностей, изложенных до настоящего момента, не решает этой проблемы. Правда, не можем не согласиться с рядом авторов /Г172I,I180]/, что разбиением основной памяти на независимые модули и соответствующим расслоением мы теоретически можем решить эту проблему использованием необходимого числа независимых модулей. На практике, oднa-j ко, рост числа модулей ограничен, причем пожалуй даже в большей степени чем рост числа процессоров. Поэтому, разбиение основной памяти на независимые модули можно и необходимо рассматривать как один из возможных способов борьбы с одновременными обращениями в основную память.

Кэш-память так-же можно очень эффективно использовать с целью понижения числа одновременных обращений к модулям основной памяти. Архитектуру мультипроцессорных систем, в которой эта функция кэш-памяти становится для нее основной, принято называть архитектурой МПС с локальной кэш-памятью.

В таких системах каждая кэш-память используется только одним процессором и в этом смысле является локальной по отношению к оставшимся процессорам МПС.

Рис. 4. Мультипроцессорная система с локальной кэш-памятью

С точки зрения -практической аппаратной реализации, архитектура с локальной кэш-памятью обладает И'тем преимуществом, что кэш-память может быть помещена на одном чипе с прикрепленным процессором, так что общее время, необходимое для доступа в кэшпамять еще больше уменьшается по сравнению с временем доступа в классическую оперативную пюмять. Этих два времени выборки в современных вычислительных системах могут ютличаться даже на порядок и более.

Идея использования кэш-памяти,как средства понижения общего числа одновременных обращений к модулю основной памяти, основана на том, что предполагает удовлетворение большинства запросов в память на лональном уровне и тем самым существенное уменьшение количества запросов в основную память со стороны каждого из процессоров.

Подчеркнем здесь один очень важный факт. Применение кэш-памяти в любой, а в том числе и в этой специфической для МПС с локальной кэш-памятью ситуации, явно предполагает возможность выделения области основной памяти на которую сконцентрированы потребности каждого из процессоров в определенном промежутке времени /гипотеза о локальности/. Значит речь идет об одном свойстве реальных программ, на предположении истинности которого, основано внедрение кэш-памяти. Этот факт нельзя забывать приступая к любому анализу архитектуры МПС с локальной кэш-памятью.

Специфика функции кэш-памяти и происходящие из этой специфики ее реальные характеристики являются причиной того, что некоторые авторы /11271,£1803/ оправданно не рассматривают локальную кэш-память в МПС просто как самый быстрый уровень в иерархии памяти, а как отдельную особенность архитектуры МПС.

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

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

Эти проблемы будут обсуждаться наряду с остальными параметра-мы архитектуры мультипроцессорных систем с локальной кэш-памятью в последующих разделах. В дальнейшем, область нашего интереса сужается только на мультипроцессорные системы указанной архитектуры.

2.3 Основные параметры архитектуры мультипроцессорных систем с локальной кэш-памятью.

В общем случае функционирование МПС с локальной кэш-памятью можно описать следующим образом: по: инициализации любого запроса в память со стороны какого-то из процессоров, проверяется наличие требуемого слова в его кэш-памяти. Если это слово присутствуI ет в его кэш-памяти /ситуация, которую мы будем называть "попа- | данием"/ запрос удовлетворяется и процессор продолжает работу. Если же слова в его кэш-памяти не оказалось /ситуация, которую будем называть "промахом"/, инициализируется подкачка из основной в кэш-память, а процессор останавливается до ее окончания.

Общепринятым способом обмена между основной и кэш-памятью является обмен блоками - множеством машинных слов, связанных обычн близостью их адрессов в основной памяти. Это значйт, что в случае "промаха" подкачивается в кэш память не только само слово, кото- I рое понадобилось процессору, но и весь блок, к которому это слово принадлежит.

Этим еще раз демонстрируется 'ориентированность применения локальной кэш-памяти на использование предположений гипотезы о локальности. Подкачка всего блока в кэш-память положительно влияет на эффективную производительность только в том случае,когда процессору действительно в скором будущем понадобится информация из окрестности слова, из-за которого и инициализирована подкачка этого блока в кэш-память.

Перейдем теперь к рассмотрению параметров архитектуры МПС с локальной кэш-памятью. Напомним только, что многие из рассматриваемых параметров не являются исключительной особенностью .данной архитектуры. Целесообразно различать два типа параметров:

1. функциональные /организационные/ параметры, которые описывают функции отдельных компонент и общую организацию МПС с локальной кэш-памятью,

2. количественные параметры, которые определяют физические размеры компонент в таких вычислитильных системах.

2.3.1 Функциональные параметры архитектуры мультипроцессорных систем с локальной кэш-памятью.

2.3.1.1 Организация отображения основной памяти в кэш-память.

•Проблема организации, точнее выбора алгоритма отображения появляется всегда, когда существует необходимость переноса информации между двумя пространствами /физическими или виртуальными/ памяти различного объема. Такая необходимость присутствует и в архитектуре с локальной кэш-памятью. Рассмотрим сейчас основные алгоритмы отображения основной памяти в кэш-память.

Простейшим по идее является ассоциативное отображение /Рис. 5. (а) /. При таком отображении любой блок основной памяти может передаваться в любой из блоков кэш-памяти. Преимуществом этого способа отображения является максимальная свобода выбора места в кэш-памяти, куда будет помещен новый блок. Следствием тао.памп ть а) о.память о.памя ть кэш б) о.память в) (г)

Рис. 5. Схемы отображения основной памяти в кэш-память, (а) ассоциативное (б) однозначное в) по секторам (г) множественно-ассоциативное кой свободы выбора является достижение максимальной эффективности использования всего пространства кэш-памяти и соответствующее уменьшение числа обменов между основной и кэш-памятью в обоих л направлениях. Недостатком ассоциативного отображения основной в кэш-память является необходимость ассоциативного просмотра всей кэш-памяти при любом запросе процессора в память, что приводит к тому, что с ростом размеров,кэш-память становится все более дорогой и/или медленной.

Противоположным по своим недостаткам и достоинствам является однозначное отображение /Рис. 5(6)/. Наждому блоку основной памати предоставляется один единственный /для него/ блок кэш-памяти, куда он может быть перенесен. Проверка наличия необходимого блока в кэш-памяти при запросе процессора является тривиальной и время ответа кэш-памяти очень маленьким. Серезным недостатком такого способа отображения является то, что интенсивность использования различных частей кэш-памяти может оказаться очень неравномерной. Проявлением этого является возможность "толкания" в каком то из блоков кэш-памяти, вызванного интенсивным попеременным использованием двух или нескольких блоков основной памяти, которые все отображены в один и тот же блок кэш-памяти. Такие явления могут привести не только к отсутствию какого-либо положительного эффекта от наличия кэш-памяти в системе, но и к серьезной деградации производительности всей системы.

Следующих два алгоритма отображения являются улучшением, в каком то смысле, предыдущих двух.

Отображение по секторам /Рис. 5(в)/ предусматривает логическое разбиение основной и кэш-памяти на секторы, каждый из которых состоит из одного и того-же числа блоков. Любой сектор основной памяти может быть отображен в -любой из секторов кэш-памяти. Обмен между основной и кэш-памятью продолжается в терминах блоков, но при "промахе" в кэш-памяти резервируется место для всего сегмента, к которому принадлежит необходимый блок, хотя реально в кэш-память переносится не весь сектор, а только этот блок. Остальные блоки сектора помечаются как недействительные. Отображением по секторам уменьшается время поиска в кэш-памяти по сравнению с ассоциативным отображением, однако проблемма неравномерности использования пространства кэш-памяти, связанная с неравномерностью использования блоков внутри сегмента становится весьма существенной. Недостатком данного подхода является и то, что при подкачке нового сектора из кэш-памяти вытесняется очень большое количество информации.

Нетрудно заметить, что причина неравномерности исспользования пространства кэш-памяти при отображении по секторам заключается в фиксированном расположении блоков внутри сектора. Множественно-ассоциативное отображение /Рис. 5(г)/ пытается преодолет этот недостаток, хотя при этом ухудшает время доступа в кэш-память. Несмотря на это, больщенство авторов /[1341,[1803/ в множественно-ассоциативном отображении видят оптимальный компромисс в организации отображения основной в кэш-память. Суть этого подхода в логическом разделении блоков кэш-памяти на N множеств, причем i- и й блок основной памяти отображается в любой из блоков j-oro множества в кэш-памяти-, где j удовлетворяет условию i=j(mod N). Заметим что множественно-ассоциативное отображение сводится к однозначному при размере множества в один блок и к ассоциативному при N=1. Являясь по практическим оценкам оптимальным в смысле соотношения скорости и стоимости /[953, Ï1803/, этот последний способ является наиболее сложным по своей логике.

2.3.1.2 Организация замещения блоков в кэш-памяти.

При наступлении "промаха" и отсутствии свободного места в кэш-памяти необходимо выбрать блок, который будет вытеснен из нэш-памяти.

В принципе возможны три типа алгоритма выбора блока, который должен быть вытеснен:

- FIFO (first-in-first-out) алгоритм, который выбирает для вытеснения блок, который дольше всего' находился в кэш-памяти,

- алгоритм случайной выборки блока для вытеснения,

- LRU (last-recently-used) алгоритм, который выбирает для вытеснения блок, который дольше всего не использовался.

При упрощенном рассмотрении архитектуры МПС с локальной кэшпамятью не замечается большое влияние организации замещения на эффективность кэш-памяти, что можно объяснить ее небольшим размером, и следовательно небольшой возможностью выбора.

Более подробные исследования / [ 1231, С1581, [ 1801, [ 182]/ показывают что LRU алгоритм дает лучшие результаты по сравнению с двумя первыми. Это можно объяснить тем, что LRU алгоритм ориентирован на использование предположений уже упомянутой гипотезы о локальности, т.е. на то, что блоки,которые использовались недавно, будут использованы вновь, а удалять из кэш-памяти, следовательно, необходимо блоки, которые дольше всего не использовались. Необходимо заметить еще, что вопрос об организации замещения нужно рассматривать и по отношению к организации отображения основной в кэш-память. Так, при однозначном отображении вообще не встает вопрос о выборе блока для вытеснения, так как этот блок определен однозначно самим алгоритмом отображения. При отображении по секторам, речь идет не о выборе блока, а о выборе сектора. При множествен но-ассоциативном отображении выбор производится не из всех блоков кэш-памяти, а из одного /всегда конкретного/ из множеств блоков кэш-памяти. Только в случае ассоциативного отображения речь идет о небходимости выбора из всей совокупности блоков кэш-памяти.

2.3.1.3 Организация выборки из основной памяти.

Данный функциональный параметр архитектуры МПС с локальной кэш-памятью определяет в каких случаях и как происходит подкачка блока из основной в кэш-память. И данной проблеме относятся два вопроса,на которые необходимо однозначно ответить.

Первый из них: необходимо ли в случае "промаха" вызванного обращением процессора в память по записи инициализировать подкачку блока в кэш-память. Постановкой такого вопроса мы впервые при рассмотрении архитектуры мультипроцессорных систем с локальной кэш-памятью пришли к рассмотрению возможности отказа от абсолитного применения идеи опосредования связи процессоров и основной памяти локальной кэш-памятью. Более конкретно, мы стали рассматривать и возможность прямого обращения процессора в основную память при выполнении команды записи.

Смысл этого частичного отступления от первоначальной идеи о роли локальной кэш-памяти мы рассмотрим в следующем разделе при рассмотрении организации восстановления содержания основной памяти. Аргументация ответа на выше изложенный вопрос также связана с выбором организации восстановления содержания основной памяти.

Второй вопрос, связанный с выборкой в кэш-память, относится к доступу в память по командам чтения. Дело в том, что подкачка блока в кэш-память, особенно при большом размере блока, осуществляется порциями. Эту подкачку возможно организовать так, что уже в первой порции блока подкачиваетса слово, из-за которого подкачка и йнициализиоована а параллельно с этим, слово передается сразу и самому процессору. Такую стратегию будем называть прямой загрузкой. Применение этой стратегии дает возможность продолжения работы процессора до окончания подкачки всего блока в кэш-память и считается /[158]/ полезным. I

При анализе общих архитектур с кэш-памятью в рамках организации выборки, в принципе, возможно и рассмотрение предварительной выборки блоков в кэш-память. Однако, в силу того, что размер кэшпамяти относительно небольшой, некоторые авторы /[95], [1803/ признают нецелесообразным применение предварительной выборки в случае мультипроцессорных систем, а другие /[1583/ подчеркивают необходимость предельной внимательности при выборе алгоритма предварительной выборки, если она применяется.

2.3.1.4 Организация восстановления содержания основной памяти.

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

Если мы не желам отступать от основных идей, изложенных в конце раздела 2.2 и в начале раздела 2.3, тогда имеем следующую ситуацию; команды записи, выполняемые процессором,.вызывают изменения необходимых слов только .а копии соответствующего блока в кэш-памяти данного процессора. Содержание этого блока в основной памяти и его копий,которые возможно существуют в кэш-памяти других процессоров остается неизменным . Только при вытеснении блока из кэшпамяти предполагается коррекция содержания этого блока в основной памят и.

Очевидно, изложенная ситуация допускает возможность ошибочной работы всей МПС, например, в следующих 'ситуациях:

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

- два процессора пользуются одной и той же областью:данных, параллельно изменяя ее. Результат их работы, так-же, как и в предыдущем случае, непредсказуем.

Приведенных два примера ясно показывают, что проблема однозначности является весьма существенной и требует полного решения.

Решению этой проблемы может сильно способствовать введение аппаратной возможности непосредственной записи в основную память со стороны каждого из 'процессоров. Такую возможность принято на-зивать прямой записью.

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

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

Таким образом, восстановление содержания основной памяти возможно двумя способами: с или без применения прямой записи.

Сравнением этих двух способов занимались многие авторы /[1581, [1801,1201/, а условия их применимости будут рассматриваться и в данной диссертации.

2.3.1.5 Разрешение проблемы однозначности в системе с локальной кэш-памятью.

Проблема однозначности является настолько важной, что ее рассмотрением занимались многие авторы /[361, [541, [1581, [1651/. В" [541 показывается /правда при некоторых предположениях/, что при выполнении процессов, каждый из которых имеет хотя бы 10% обращений в общий участок памяти, проблема • однозначности является г основным источником деградации производительности МПС.

Перейдем к краткому изложению фактов о проблеме однозначности

Причиной проблемы однозначности является следующее: а/ существование общих /для нескольких процессоров/ областей данных, т.е. возможность существования различных копий одного и тогоже блока в кэш-памяти различных процессоров, б/ миграция процессов с одного процессора на другой, т.е. возможность ситуации, в которой содержание кэш-памяти в момент активизации процесса не соответствует содержанию в момент прерывания этого процесса.

Скажем сразу, что причины второго типа характерны для МПС работающих в режиме мультипрограммирования. Эта сторона проблемы однозначности■ не будет предметом внимания данной диссертации.

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

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

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

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

В этом смысле возможна оптимизация динамического подхода введением глобальной таблицы состояния блоков основной памяти и локальных таблиц состояния кэш-памяти. Подробное рассмотрение такого подхода излагается в Е54!1 , но указывается что и он обладает определенными недостатками:

1. хотя интенсивность обмена сигналами и понижена, она остаетс? значительной,

2. глобальная таблица состояния блоков основной памяти, как интенсивно используемый общий ресурс,становится "узким местом" МПС. Предлагается решейие этой проблемы размещением этой таблицы в специальную сверхбыструю память или ее распределение по модулям основной памяти, так чтобы данные о блоках некоторого модуля находились в самом этом модуле,

3. число действий, необходимых для удовлетворения обращения в память становится большим /проверка наличия блока в кэшпамяти, инициализация подкачки, подкачка с проверкой наличия правильной копии блока в основной памяти, выполнение команды и получение ответных сигналов от других процессоров/ что требует чрезвычайных возможностей устройства управления и контрольных устройств памяти.

Заметим, что как статический, так и динамический подход предусматривают возможность прямой записи. В МПС, в которых такая возможность отсутствует проблема однозначности становится принципиально существенной. Решать эту проблему можно, например, используя идеи динамического подхода. Глобальная таблица состояния блоков используется тогда и для указания места нахождения пос \ ледней /корректной/ копии блока. Подкачка блока в любую кэш-память, в таком случае, начинается с определения местонахождения правильной копии блока и, при необходимости, форсирования вытеснения этой копии блока из кэш-памяти процессора, на которой она находится.

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

2.3.1.6 Однородность кэш-памяти'.

Как и на многих других уровнях организации памяти, в случае кэш-памяти возможно функциональное /т.е. по назначению/ разделение пространства кэш-памяти. !

Разделение на область команд и на область данных обеспечивает чтобы блоки с командами не вытеснялись слишком рано из кэш-памяти из-за интенсивного использования данных. Такое разделение, однако, может привести к очень нерациональному использованию кэш-памяти. *

Разделение кэш-памяти на область системных команд и данных и на область пользовательских команд и данных существенно в случае, когда происходит частое переключение процессоров с одной активностк на другую /1951/, что характерно, например, для работы в режиме мультипрограммирования.

2.3.1.7 Архитектура системы связи основной и кэш-памяти.

С ростом числа процессоров и модулей1: основной памяти усложняется вопрос их взаимосвязи. В МПС с локальной кэш-памятью проблем'а накладных расходов, связанных с системой связи процессоров и модулей основной памяти в значительной степени смягчается из-за того, что предполагается что большинство запРосов в память удовлетворяется на локальном уровне, а значит без участия системы связи. Уже в МПС с общей кэш-памятью эта проблема встает значительно серьезнее. Тем не менее, и в МПС с локальной кэш-памятью следует рассматривать возможные способы соединения Процессоров /т.е. их кэш-памяти/ с модулями основной памяти, в смысле оптимизации этого соединения /11263/.

Простейшим по аппаратной реализации является способ соединения по общей шине. Такой способ, однако, обладает относительно маленькой эффективностью даже при небольшом числе процессоров в системе, так как одновременно общей шиной'может пользоваться только одна пара ресурсов МПС.

Некоторым развитием этого способа соединения, является система с несколькими шинами связи, каждая из которых может быть использована всеми или группой процессоров для доступа к произвольному или определенному модулю основной памяти. Простейшим по идее, но сложнейшим по аппаратной реализации является полный матричный переключатель. Противоположно общей шине, эффективность такого способа связи не уменьшается с ростом числа элементов МПС /процессоров или модулей/, т.к. полный матричный переключатель обеспечивает параллельную связь всех пар, которые этого потребуют. Но, громоздкость, сложность, а следовательно и стоимость такого переключателя экспоненциально растут с ростом числа элементов.

Примером компромиссного варианта между шиной и полным матричным переключателем является пример дельта-сети /£1263/, которая, с одной стороны, болев прост ая по аппаратной реализации чем полный переключатель /ее стоимость растет с логарифмической скоростью/, а, с другой стороны, по эффективности дельта-сети близки к полным переключателям.

Рассматривая архитектуру связи основной и кэш-памяти, нельзя не упомянуть понятие ширины -линии связи. Чем шире линия связи, чем больше информации передается за один раз по этим линиям, тем быстрее может происходить обмен между основной и кэш-памятью, и тем меньше потенциальная возможность превращения системы связи в "узкое место" МПС.

2.3.2 Количественные параметры.

2.3.2.1 Число процессоров.

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

Стоимость процессоров настолько падает, что она практически не 'является препятствием наращивания их числа. Однако, целесообразность неограниченного увеличения числа процессоров следует рассматривать в свете явления деградации производительности МПС, т.е. взаимосвязи числа процессоров со сложностью и стоимостью остальных компонент МПС, которые необходимы для того, чтобы этот рост номинальной производительности отразился в производительности эффективной.

2.3.2.2 Число модулей основной памяти, их величина и расслоение.

В разделе 2.2 мы уже указывали на то, -что при возможности неограниченного увеличения числа модулей, можно было бы решить проблему одновременных обращений к модулям основной памяти, из-за которой в основном и изучаются МПС с локальной памятью. Разбиение основной памяти на практике ограничено требованием разумной простот контрольного устройства, реализующего "логику" обращений в память.

Аппаратное разделение основной памяти должно обязательно сопровождаться расслоением основной памяти. При рассмотрении архитектуры с локальной кэш-памятью обычно говорят о расслоении на уровне блоков, а не слов. Это значит, что принадлежность какого-либо слова какому-то модулю не определяется ни по крайним левым, ни по крайним правым разрядам адреса, а по группе разрядов, находящейся в середине адреса, и смещенной ближе к правому или левому его концу Возможно конечно, и рассмотрение расслоения на уровне слов. Учитывая тот факт, что обмен между основной и кэш-памятью осуществляется на уровне блоков, нетрудно заметить что расслоение основной памяти по словам может привести к ускорению доступа в частных случаях, но в целом такое расслоение распределением нагрузки по всем модулям, может аннулировать эффект локальности, используемый в кэш-памяти. *

Размер модулей, а тем самым и размер основной памяти подчиняются всем тем закономерностям, которые характерны для МПС, несмотря на присутсвие или отсутсвие кэш-памяти.

2.3.2.3 Размер кэш-памяти.

Мы уже упомянули что основной характеристикой кэш-памяти является ее большая скорость. При рассмотрении функциональных параметров мы неоднократно замечала что алгоритм доступа, а прежде всег.о постоянные проверни наличия требуемой информации в кэш-памяти, являются весьма сложными. Этих два в каком то смысле про-тироречивых факта объясняют, почему кэш-память остается и сегодня относительно дорогой. Поэтому ее размер всегда является копромиссог между неограниченными потребностями процессоров в такой памяти и разумной стоимостью вычислительной системы в целом.

На практике мы сегодня имеем дело с кэш-памятью размером от 0.25 до 16 Н байт.

2.3.2.4 Размер блока памяти.

Как показывают многие анализы /С953,С182Д/ размер блока является одним из важнейших количественных параметров архитектуры МПС с локальной кэш-памятью.

Наблюдения показали, что в начале с ростом размера блока увеличивается эффективная производительность МПС, что очевидно связанно с тем, что в один обмен между основной и кэш памятью подкачивается больше информации, котврая действительно необходима процессору. »

Однако, начиная с некоторого критического размера, увеличение размера блока не способствует улучшению, или даже отрицательно влияет на показатели производительности МПС. Это можно объяснить многими причинами: уменьшением полезности "добавочной" информации при подкачке блока, ростом количества информации, которая вытесняется из кэш-памяти при подкачке нового блока, ростом времени обмена между основной и кэш-памятью, что вызывает повышенную нагрузку основной памяти и системы связи основной с кэш-памятью итд.

Правильное определение величины блока поэтому очень важно для достижения большей производительности МПС. Некоторые результаты /[182]/ указывают на то, что оптимальным является размер блока от 16 до 256 байт.

2.3.2.5 Время выборки и время обмена между основной и кэш-памятью.

Нет необходимости особенно указывать на то, что чем быстрее основная пямять, тем лучше эффективная производительность МПС, так как уменьшается время обмена между основной и кэш-памятью, которое зависит исключительно от скорости выборки из основной памяти и рассмотренных характеристик системы связи основной и кэш-памяти.

2.4 Окончательное определение задачи и выбор метода решения.

Уже было сказано, что предметом нашего внимания являются мультипроцессорные системы с локальной кэш-памятью и проблема ■ одновременных обращений в память, возникающая в таких системах. Целью данной диссертации является разработка средств для анализа подобных вычислительных систем, в первую очередь, для анализа степени разрешения проблемы одновременных обращений в основную память в таких системах с локальной кэш-памятью.

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

Предшествующее относительно подробное рассмотрение и систе- ■ матизация параметров архитектуры МПС с локальной кэш-памятью должны были показать и то, что класс вычислительных систем, характеризующийся такой архитектурой памяти весьма обширен, в смысле многообразия различных.номбинаций параметров,определяющих каждую реальную систему этого класса. Таким образом, средство анализа, ' -которое разрабатывалось, должно было быть гибким и универсальным для как можно большего подмножества класса вычислительных систем подобной архитектуры и ориентировано, прежде всего, на анализ зависимости накладных расходов по обмену с памятью от параметров архитектуры МПС с локальной кэш-памятью. Другими словами; необходимс было разработать средство для анализа зависимости степени деградации производительности МПС с локальной кэш-памятью, вызываемой обращениями в память, 'от параметров архитектуры системы. Имея такое средство, можно ответить какими выбрать значения параметров, чтобы минимизировать накладные расходы по обмену с памятью используя принципиальные возможности МПС с локальной кэш-памятью.

Создание реальных систем и измерение их производительности, как средство решен ия поставленной задач и практически исключено, прежде всего из-за многообразия и численности класса вычислительных систем исследуемой архитектуры.

Характер поставленной задачи указывал, что к ее решению необходимо подойти используя средства моделирования -метода, который сегодня получает все большее распространение из-за многих его положительных сторон.

Большинство авторов, занимающихся проблемой архитектуры МПС с локальной кэш-памятью, пошло по пути создания аналитических /вероятностных или детерминированных/ моделей. Создание аналитической модели и особенно получение результатов моделирования из такой модели является, пожалуй, самым недорогостоящим методом анализа. Результаты, полученные таким моделированием имеют, несомненно, фундаментальное значение. Однако, аналитическое моделирование обладает некоторыми недостатками:

- во многих случаях, необходимо формально упрощать структуру моделируемого объекта, чтобы аналитическая модель имела аналитическое решение,

- при рассмотрении многих существенных параметров /а это преждЕ всего относится к функциональным параметрам/ приходится заново : создавать всю модель для каждого из значений параметра.

Этот второй недостаток аналитического моделирования предопределил обращение к средствам имитационного моделирования при peшeни^ поставленнойза'дачи.

Таким образом, с целью получения средства анализа зависимости степени деградации производительности МПС с локальной кэш-памятью от параметров такой архитектуры, создана имитационная модель, охватывающая большое подмножество вычислительных систем указанного класса.

2.5 Поведение программ и возможности его моделирования.

Перед тем, как перейти к описанию самой модели, необходимо указать на еще один параметр анализа эффективной производительности МПС с локальной кэш-памятью, который мы еще непосредственно не упоминали, а который сейчас рассмотрим в свете выбранного метода решения поставленной задачи и анализу которого, посвятим особое внимание в данной диссертации.

Речь идет о влиянии характеристик программ, выполняемых в системе, на эффективную производительность этих систем. Не вызывает никаких сомнений тот факт, что эффективная производительность всякой вычислительной системы в конечном счете во многом зависит от этого важного параметра. Исключением не являются и МПС с лока.льнсуй кэш-памятью. Тем более, что, как неоднократно подчеркивалось, само внедрение кэш-памяти в МПС обосновывается гипотезой о локальности, т.е. одной предполагаемой характеристикой реальных программ.

Из сказанного следует, что любой анализ эффективной производительности, претендующий на достоверность, должен учитывать и влияние характеристик программ на эту производительность.

При моделировании, в зависимости от объекта и цели анализа, как параметры анализа 'используются различные характеристики программ.

Ими являются, например, такие глобальные характеристики, как максимальная потребность в оперативной памяти или во времени центрального процессора.

Часто, а так и в нашем случае, необходимо значительно более подробно анализировать влияние характеристик программ на эффективную производительность вычислительной системы. Токой более подробной характеристикой программ может'являться поведение., программ . Этим термином мы называем характеристику последовательности обращений в память, которая возникает в динамике счета программы. Это поведение имеет следующих три аспекта:

1. временной, т.е. характеристику частоты обращений в память,

2.'последовательностный /пространственный/, т.е. характеристику последовательности адрессов слов,к которым происходит обращение в динамике счета,

3. логический, т.е. характеристику логической зависимости между двумя обращениями в память.

Не трудно заметить, что поведение реальных программ зависит от многочисленных факторов: начиная, прежде всего, от самого алгоритма, но нончая и спецификой трансяторов или даже опытностью программиста.

Все это указывает на то, что моделирование поведения программ является весьма сложной задачей.

В аналитических моделях /Г341, [ 127] , [ 1371, [ 182]/ приходится формализовать поведение программ, чтобы уменьшить число параметров, характеризующих это поведение, и так обеспечить включение этого поведения в рассмотрение. Эта формализация проявляется во введении некоторых вероятностых' величин и построении вероятностных моделей динамического поведения программ на основании этих величин. Среди величин, используемых для описания поведения программ.и следующие:

В - вероятность, что процессор инициализирует обращение в памят в течении единичного интервала времени,

Ь - вероятность, что обращение в память процессора является "промахом",

VI - вероятность, что обращение является командой записи.

Исходя из этих и подобных параметров, разрабатывались различные аналитические модели поведения программ. Среди них наиболее из вестны:

1. Модель независимого обращения / [ 127] ,.[ 1 371 /, которая утверждает, что вероятность обращения к какому-то конкретному блоку является постоянной для каждого блока. Простейшей формой модели независимого обращения является модель равновероятного /случайного/ обращения, в которой предполагается, что вероятность обращения для всех блоков основной памяти одинакова,

2. Модель рабочего множества / [46],[1373/, разработка которой связана еще с изучением постраничной организации памяти в классических вычислительных системах. Эта модель строится на предположении существования дискретной вероятностной функции времени '^'1), где является частью уже выполненных команд, для которых предыдущее обращение по тому же адрес было 1 единиц времени тому назад. Другими словами, функция показывает что вероятность обращения по некоторому адресу в момент t2 равна где ^-время последнего предыдущего обращения по тому же адресу.

3. Стековая модель /11371/, идея которой состоит в предположении существования стека, содержащего номера всех блоков основной памяти. В вершине стека всегда находится номер блока, к которому было самое последнее обращение в память. Стековая модель предполагает существование дискретной вероятностной функции р(1), которая дает вероятность обращения •к блоку, находящемуся на 1-ом месте в описанном стеке. Функция р(1) считается независимой от всех прочих факторов, . кроме места блока в стеке.

Иногда используются и другие модели, которые взаимно отличаются, впрочем как и приведенных три, степенью абстрактности ., подробности и точности имитирования поведения программ, так и количеством данных и необходимым временем для их разработки.

Сказанное раскрывает й основные недостатки аналитических моделей поведения программ. Во-первых, совсем нетривиальной задачей является определение значений величин , и тем более вида функции f{^) или р(1) для реальных программ. Во-вторых, для каждой программы необходимо совсем заново определять эти параметры, что говорит о том, что их получение для достаточно большого числа-Т1ро-грамм является весьма дорогостоящим. Основным, однако, недостатком аналитических моделей поведения программ является то, что при их использовании в глобальных моделях вычислительных систем, модели поведения программ приходится максимально упрощать, если только, мы желаем получить какие-либо результаты анализа глобальной модели. В таких ситуациях модель поведения программ может стать чрезмерно грубой, а это крайне нежелательно. Этот факт явился дополнительным аргументом для отказа от аналитического моделирования и обращения к средствам имитационного моделирования.

При моделировании поведения программ в имитационных моделях существуют две принципиальные возможности.

Первая состоит в повторении идей, используемых в аналитических моделях, но только средствами имитационного моделирования. При таком подходе мы получаем модель со стохастическими элементами, и встречаемся опять с проблемой определения стохастических параметров для реальных программ.

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

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

1. трассировочные записи такого уровня подробности, какой необходим нам, обычно не содержат временных соотношений между двумя событиями /конкретно, обращениями в память/,

2. основной проблемой является то, что мы на сегодняшний день не располагаем трассировочными записями выполнения программ на мультипроцессорных системах, т.е. трассировочными записями програмп,которые были разделены на независимые части и паралельно выполнялись на различных процессорах МПС.

С желанием преодоления этих трудностей, в данной диссертации сделана попытка искусственной генерации трассировочной записи, которая должна максимально соответствовать записи выполнения программ в только что упомянутых условиях счета в МПС.

2.6 Структура расходов на обмены с памятью и мера производительности.

Как мы определили в разделе 2.4, в центре нашего внимания находится взаимоотношение накладных расходов по обмену с основной памятью и параметров архитектуры МПС с локальной кэш-памятью. Имея ввиду такую направленость дальнейшего изучения,: рассмотрим понятие производительности так, как оно употребляется в данной диссертации.

Поскольку мы интересуемся прежде всего накладными расходами по обмену с основной памятью, мы не будем рассматривать, а точнее будем считать, что отсутствуют всякие другие накладные расходы в вычислительной системе /работа управляющих программ, время, необходимое для установления связи между процессором и модулем основнок памяти и.т.д./. Таким'' предположением мы »конечно ,удаляемся от реальной ситуации, но получаем возможность подробного и изолированного изучения характеристик интересующего нас типа накладных расходов.

Другими словами, мы вместо общей ситуации, показанной на Рис.1 рассматриваем упрощенную ситуацию:

Полезная работа процессоров /работа прикладной программы/ Блокировки по обмену с основной памятью г

С1 "■'

Рис. 6. Состояния мультипроцессорной системы, рассматриваемие в данной работе.

При таних предположениях, как меру производительности можно рассматривать /полезное/ время работы процессоров. Номинальная производитильност /П / в таком случае равна времени работы / при н моделировании это количество времени, которое моделируется/ умноженному на число процессоров: п

П = Л^ Ь = Ь ' п н г=1 мод мод

Эффективная производительность /П / равна разности номинальной производительности и времени, проведенном всеми процессорами в состоянии блокировки из-за ожидания окончания обмена между основной и кэш-памятью: п г п г

П = Л, (Ь )= П - Л. Ь, э г=1 мод бл н г=1 бл

Заметим, что в нашем случае эффективная производительность равна номинальной, если необходимая информация всегда будет ноходится в кэш-памяти к моменту, когда она действительно понадобится процессору.

Учитывая выше изложенные принципы функционирования МПС с локальной кэш-памятью, нетрудно заметить, что в общем случая структура времени, проведенного в состоянии блокировки соотверствует струнтуре изображенной на Рис. 7.

Разработанная имитационная модель МПС с локальной кэш-памятью обеспечивает возможность анализа всех составных частей исследуемого типа накладных расходов:

Общее время проведенное в состоянии блокировки из -за обмена с основной памятью

Время подкач- Простой Время ки блоков из-за возврата из основной одновременного блоков из в -----.} обращения ■ е----- кэш-памяти кэш в в память основную основную память память

Чистое время подкач к и блонов из основной в кэшпамять

Простои из-за Одновременного обращени? в основную память при подк ач ке блока в кэшпамять»

Простои из-за одновременного обращения в основную память при воз врате блока в основную память

Чистое время возврата блоков :из кэш-в основную память

Время межпроце ссорных остановов по внеоче редному возврату блоков из•кэш в основную память

Рис. 7. Структура накладных расходов по обмену с памятью

ГЛАВА 3. писание имитационной модели мультипроцессорной системы с локальной кэш-памятью.

3.1 Общая структура системы моделирования.

Программная имитационная модель разрабатывалась на вычислительной машине и NIV А С 1 100/42 средствами языка программирования ПАСКАЛЬ, существующего на данной машине /С162]/. Средства языка ПАСКАЛЬ, которые использовались являются самыми стандартными /СЭ21/, так что при желании использования созданной модели на другой вычислительной установке, может появиться только необходимость минимальных изменений в части, связанной с вводом-выводом.

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

Таким образом общая структура системы моделирования получилась следующей:

Статистика о прогонке моде л

Рис. 8. Общая структура системы моделирования

- где

МРБ1N

М Р 5 Б IМ МРБОиТ программа, обеспечивающая задание параметров моде- ■ лирования в диалоговом режиме, программа выполняющая само имитационное моделирование программа, обеспечивающая первичную обработку результатов моделирования и их выдачу в форме таблиц.

Текст указанных программ находится в Приложении 1.

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

С целью |обеспечения статистической обработки результатов моделирования, дополнительно создана программа /МРБРЯЕББ/ "развер-тЦвания" результатов .моделирования в форму, приемлемую для суще

RUNIN .

CONFIG ч s

RUNOUT, э

RESFILE

Рис. 9. Статистическая обработка результатов моделирования ствующих статистичесних пакетов программ. В конкретном случае, для пакета SS /Statistical System/, разработанного в Загребском университете /С1Б43/.

Перейдем теперь к более подробному рассмотрению самой модели.

3.2 Фиксированные параметры архитектуры и общие предположения в модели МПС с локальной кэш-памятью.

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

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

Во-вторых, анализ результатов такого всеобъемлющего моделирования был бы чрезмерно затруднен его многофакторностью.

С целью упрощения модели пришлось провести дальнейшую конкретизацию, выбором значений некоторых функциональных параметров архитектуры, изменение которых в модели стало невозможным.

Так, отображение основной в кэш-память предполагается ассоциативным, т.е. предполагается, что любой блок основной памяти может занимать любое место в кэш-памяти. При этом не рассматриваются затраты ассоциативного просмотра кэш-памяти, а считается, что кэш память настолько быстрая, что удовлетворяет запрос в течении единичного такта времени /при условии, конечно, что необходимая инф-'ормация уже находится в ней/.

Замещение блонов в нэш памяти так-же происходит всегда по одному и тому же алгоритму - LRU алгоритму, т.е. для вытеснения выбирается блон, который дольше всего не использовался.

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

Организация выборки из основной памяти, организация восстановления содержания основной памяти и, в каком то смысле, способ разрешения проблемы однозначности остаются задаваемыми параметрами системы моделирования.

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

3.3 Моделирование поведения программ.

Задача моделирования поведения программ возложена на генератор обращений в память, реализуемый процедурой SPROGRAM(J) в программе MPSSIM. Задача названной процедуры в любой такт времени определить активность процессора J в зависимости от в начале заданных номера стратегии /MEMREFST/, ее параметра /MEMREFPR/, а также и оттекущего состояния моделируемой системы. Если процессор не занят ожиданием окончания предыдущей активности, тогда генератор обращений в память может определить для данного працессора одну из следующих активностей в предстоящем такте: а/ обращение в память по записи (3) б/ обращение в память по чтению (Ч) в/ обращение в память по чтению последнего .состояния, и, возможно, последующей записи (43) г/ активность без обращения в память /например, арифметическая операции с использованием регистров (х).

Кроме типа активности, генератор обращений в память выдает и адрес /точнее номер блока/ по которому происходит обращение /дла активностей типа а/,б/ и в//.

Из сказанного следует, что по своей структуре информация, выдаваемая генератором обращений в память, есть своего рода трассировочная запись, проецированная на временную ось. Характер этой трассировочной записи зависит прежде всего от выбранной стратегии и ее параметра.

В разработанной модели предусмотрено десять стратегий работы генератора обращений- в память. Предполагается" ' что все процессоры системы работают по одной и той же стратегии. Минимальные изменения необходимы в системе моделирования дня получения возможности моделирования режима, в котором различные процессоры работают по различным стратеги ям.

Перейдем к рассмотрению стратегий работы генератора обращений в память.

Стратегия №5 является реализацией модели случайного обращения, которая применяется в аналитических моделях,при моделировании поведения программ. Параметром этой модели является вероятность того, что обращение в память является командой записи.

Стратегия №6, которая является видоизменением стратегии №5, дает возможность задания степени локальности при обращении в память. Блок, к которому производится обращение, опять выбирается случайно, но после того, как блок выбран, несколько последующих обращений относится к тому же блоку. Параметр этой стратегии определяет часть блока /в процентах/, которая используется перед тем, как обращения переносятся на следующий /случайный/ блок. Вероятность того,что обращение является записью в этой стратегии постоянна, и равна 0.25.

Оставшиеся стратегии задуманы так, чтобы воспроизводили трассировочные записи некоторых вполне конкретных программ-алгоритмов. При этом предполагалось следующее:

- все промежуточные и вспомогательные данные являются чисто локальными и время доступа к ним всегда равно времени доступа в кэш-память,

- все арифметические операции и операции сравнения выполняются на регистровом уровне, время их выполнения равно времени доступа в кэш-память,

- все процессоры решают одну и ту же задачу, распараллеленную соответствующим образом,

-выборка команд не рассматривается.

Ряд стратегий воспроизводит трассировочные записи программ умножения двух многочленов: с (х) = а (х) * Ь (X)

Параметр во всех стратегиях определяет степень многочленов а и Ь . Многочлены расположены в последовательных блоках основной памяти. В первом блоке расположены данные, обеспечивающие синхронизацию и распределение работы.

Различие между стратегиями этой группы состоит в способе разделения задачи умножения многочленов на части, которые выполняются параллельно на процессорах МПС. Включение всех этих стратегий в генератор обращений в память данной системы моделирования имеет своей целью показать способ анализа распараллеливания конкретного алгоритма, используя рассматриваемый подход к моделированию поведения программ.

В стратегии №2 распараллеливание осуществлено следующим образом: на запрос каждый процессор "получает" следующий по очереди коэффициент многочлена Ь(х), умножает его на все коэффициенты многочлена а(х) и произведения добавляет соответсвующим коэфици-ентам многочлена Расписывая это по тактам получаем:

1 - запрос нового коэффициента многочлена - 43 (j)

2-- i:=1 х

3 - читай b(j) Ч (b(j))

4 - ч итай а ^'/ • ч U(i))

5 . 1:= а(1) * b(j) х

5 c(i+j):= c(i+j) + 1 чз (c(i+j))

7 - i:=i+1 x

0if i>MEMREFPR then 1 else 4 x или в форме некоторой схемы:

43 а I

1 2 7

3 4 5 ь ч

43 ч+д ч х х х х

Рис. 10. Схема трассировочной записи по 2-ой стратегии

В стратегии №7 та же задача умножения многочленов решается распараллеливанием иным способом: на запрос каждый процессор "получает" очередной коэффициент результирующего многочлена с(х) и читает все необходимые пары коэффициентов многочленов а(х) и Ь(х), постепенно добавляя их произведения к полученному' коэффициенту из с(х). В этом случае схема трассировочной записи выглядит по-другому:

43 т ==1 4 а1 Ч

Ьк-1 аГьк-1

1:=т+1 х 3 х х X к с к

Рис. 11. Схема трассировочной записи по стратегии №7.

Стратегия N28 оптимизирует стратегию №7, предполагая, что сумма хранится в локальной переменной, и только в конце ее значение присваивается коэффициенту из с(х). Тогда имеем произведений а. * Ь

1 и

43 к Л аТ кИ а1*Ьк-1

1 :=! + а,*Ь к-1'

1:=т+1

1 2 3 4 Ь ь 8 9 х х х X С к

Рис. 12. Схема трассировочной записи по стратегии №8,

Возможна дальнейшая оптимизация стратегий №2 и №8, состоящая в предположении, что каждому процессору заранее известна его область коэффициентов внутри многочленов Ь(х) /для стратегии №2/ или с(х) /для стратегии №8/, в связи с чем отпадает необходимость обращения в общую часть памяти при-переходе на новый участок работы. Для стратегии №9, являющейся оптимизацией стратегии №2, имеем:

Рис. 13. Схема трассировочной записи по стратегии N29.

Для стратегии №10, которая является оптимизацией стратегии №8 в изложеном смысле, полумаем следующую схему трассировочной записи

Рис. 14. Схема трассировочной записи по стратегий N210.

В стратегии №1 имитируется трассировочная запись параллельного алгоритма умножения двух квадратных матриц: С = А х В. Параметр стратегии задает размер этих матриц. Матрицы расположены последовательно по блокам основной памяти, элементы матрицы располагаются в памяти последовательно по строкам. Распараллеливание осуществлено так, что на запрос, каждый процессор получает номер следующего элемента результирующей Iматрицы С и вычисляет его, как сумму произведений элементов строки матрицы А и столбца матрицы В.

Схема генерируемой трассировочной записи этого алгоритма по' и лучается следующей:

Рис. 15. Схема трассировочной записи по стратегии №1.

Стратегия №3 - генерирование трассировочной записи параллельного суммирования массива чисел П. Процессор, на запрос, получает очередной "кусок" массива М, суммирует его, и в конце полученную сумму добавляет к общей|сумме. Параметр определяет длину "куска". Схема получается следующей:

Рис. 16. Схема трассировочной записи по стратегии №3.

Наконец, в стратегии №4 моделируется алгоритм просмотра таблицы Т, с целю определения числа вхождений и порядковых номеров определенного значения в этой таблице. Параметр задает длину "куска", который выдается процессору на его запрос для' просмотра. Предполагается, что число вхождений искомого элемента равно 0.1 размера всей таблицы. Схема трассировочной записи получается следующей:

1 2 3 Н I 4 5 6 7 8 9

43 X Ч X 3 X X X 43 к ты В1 №1 В1. №1

1 :=0 1 :=0 1 1:=1+1 1" :=И+1 ?

Рис. 17. Схема трассировочной записи по стратегии- №4.

Автор сознает, что в при веденных примерах генерируемые трассы далеки от абсолютного сходства с реальными трассами решения рассматриваемых проблем и с последовательностной и, особенно, с временной точки зрения. Однако, даже приведенные примеры значительно ближе к реальности!' чем любой из подходов, применяемых в аналитических моделях.

Особенно важным преимуществом рассмотренного подхода к модели- I рованию поведения программ,на наш взгляд," является принципиальная возможность сколь угодно точного приближения к реальным ¡трассам как в последовательностном, так и в временном аспекте/. Это дости гается увеличением числа элементарных шагов, на которые разбивается алгоритм. Включение новой стратегии в генератор обращений в память не составляет большой трудности. Требуются лишь элементарные навыки в программировании на ПАСКАЛЬ-е и желание рассмотрения алгоритма с точки зрения его расщепления на элементарные шаги, приведенные в начале данного раздела. Взамен мы получаем возможность анализа применимости рассматриваемого алгоритма на данной архитекуре МПС, определения оптимальных параметров архитектуры для данного алгоритма, или, наоборот, определения оптимального алгоритма решения задачи в условиях конкретной архитектуры .

Таким подходом к моделированию поведения программ автор старался максимально использовать преимущества имитационного моделирования и одновременно преодолеть проблему отсутствия подходящих трасс выполнения распараллеленных реальных программ.

3.4 Входные параметры модели и блок-схемы программ моделирования.

Входными параметрами модели являются:

1. МиМРКОСЕ - число процессоров,

2. ГШММООШ. - число модулей основной памяти,

3. МиМВЬМОЭ - число блоков в каждом модуле,

4. МиМВЮАС - число блоков в каждой кэш-памяти,

5. МиМИВЬ - число слов в каждом блоке /размер блока/,

6. ВиБИЮТН - ширина линии связи между основнй и кэш-памятью,

7. ТРБиБЫИ - время выборки и передачи ВиБИЮТН слов из основной в кэш-память /выраженное в 0.1 долях такта/, Назначение этого параметра - определять соотношение скорости основной и кэш-памяти, задание расслоения основной памяти: 1 - без расслоения /последовательно/, 2-е расслоением,

3 - случайный разброс блоков" по модулям основно памя т и,

4 - задание расположения блоков по модулям в диалоговом режиме, число тактов, которое должно длиться моделирование, наличие или отсутствие прямой загрузки, наличие или отсутствие прямой записи, номер стратегии генератора обращений в память, т.е. стратегии моделирования поведения программ, параметр, передаваемый генератору обращений в памя т ь.

Значение двух последних параметров, связанных с моделированием поведения программ, мы практически рассмотрели в предыдущем разделе

Моделирование прямой загрузки проводится именно в том смысле, в котором и обсуждалось в разделе 2.3.1.3.

Рассмотрим подробнее моделирование прямой записи и тесно, связанный с ним способ решения проблемы однозначности.

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

В. виНБТв д< гшмсуаЕ /

10. АИВШАГГ

11. ВИМАБЕ

12. МЕМЯЕРБТ

13. МЕМЯЕРРЯ " полагается существование специальной команды чтения, которая форсирует подкачку блока в кэш-память, независимо от возможного его присутствия в кэш-памяти.

Таким образом, команда чтения в архитектуре с прямой записью реализована следующим образом:

Рис. 1В. Чтение в архитектуре с прямой записью.

В этой же системе команда записи тривиальна по своей логике:

Рис. 19. Запись в архитектуре с прямой записью.

В случае если рассматривается архитектура без прямой записи, подкачка блока в кэш-память предусматривается по любому обращению в память, вызывающему возникновение ситуации "промаха". Проблема однозначности решается динамическим подходом /неявно предполагается существование глобальной таблицы состояния блоков, хот ; время задержки по доступу к ней не учитывается/. В данном случае команды чтения и записи усложняются и реализованы следующим образом: а/ чтение б / 3:а п и с ь

Рис. 21. Запись в архитектуре без прямой записи. где

Рис. 22. Процедура подкачки блока в' архитектуре без прямой записи.

-Мы рассмотрели все входные параметры модели, унаэали на способ реализации влияния функциональных параметров архитектуры на процесс моделирования, т.е. на результаты моделирования.

Осталось только, хотя бы грубо, описать процесс моделирования, что можно :сделать следующей схемой:

3.5 Выходные результаты модели и форма их выдачи.

Реально, при моделировании измеряються следующих 17 величин:

1. ВР^^Ш - общее число выполненных команд чтения,

2. ВЯМ№ - общее число выполненных команд записи,

3. ВЯТМСЯ - общее число "промахов" по командам чтения,

4. ВР^ТМС№ - общее число "промахов" по командам записи,

5. В!^52М - общее число одновременных обращений в основную память при подкачке блока из основной в кэш-память я

Б. \ZRSZM - общее' время простоя процессоров из-за одновременных обращений в память при подкачке блока из основной в нэш-память, 7. \ZRTBMC - чистое общее время передачи блоков из основной в кэш-память,

В. - общее время занятости модулей основной памяти,

9. ВРБУВМ - общее число возвратов блоков из кэш в основную памят ь,

10. V Я Б V В М - чистое общее врема передачи блоков из кэш в основ^ ную память,

11. BRSZMVB - общее число одновременных обращений в память при возврате блоков из кэш в основную память,

12. VЯБVВ - общее время простоя процессоров из-за одновременных обращений в основную память при возврате блоков из кэш в основную память,

13. ВР52Р2В - общее число межпроцессорных остановов по требованию откачки блоков из кэш в основную память,

14. VЯБ7Р7В - общее время, теряемое из-за межпроцессорных остановов по требованию откачки блоков,

15. \ZRBLMEM - общее время, которое простаивает основная память из-за ожидания окончания активности процессора, из кэш-памяти которого, должен быть откачан блок,

1В. BRSZMW общее число ситуаций одновременных обращений в ос-' новную память при прямой записи, 17, VRSZMW общее время, которое теряется из-за одновременных обращений в память при прямой записи.

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

Программа MPS0UT осуществляет первичную обработку этих результатов, в том смысле, что на основании этих результатов выдает 51 таблицу /см. Приложения/. Различные элементы каждой таблицы относятся к различным парам значений аргумента и параметра данной прогонки. В таблицах даются значения самих измеряемых величин, их суммы, имеющие некоторый дополнительный смысл, средние значения числа случаев возникновения определенных ситуаций, вероятность их возникновения, среднее и относительное время, потерянное из-за этих ситуаций. Последовательность таблиц заканчивается таблицей эффективной используемости процессоров и происходящей из нее таблицей эффективной вычислительной мощности, выраженной в условных единичных процессорах.

3.6 0 верификации модели.

Обязательный вопрос, возникающий при всяком анализе, основанном на моделировании, есть вопрос соответствия модели моделируемой системе.

Этот вопрос становится весьма сложным в ситуациях, когда объектом моделирования является несуществующая либо недоступная система, так как отпадает возможность непосредственного сравнения реальных показателей и результатов моделирования. Именно в такой ситуации находимся и мы.

Несмотря на сделанные предположения, класс МПС,который представлен описанной имитационной моделью довольно обширен, а так-же и неоднороден в силу присутствия функциональных параметров архитектуры в числе параметров модели. С другой стороны, автору были недоступны какие-либо показатели работы реальных представителей рассматриваемой архитектуры МПС, наверное и потому, что на сегодняшний день существует минимальное число реальных систем такого типа и сами они находятся еще на этапе разработки и усовершенствования .

В такой ситуации остается только возможным последовать совету Д.Феррари /Е631/ и признать моделируемую систему некоторой концептуальной моделью и проверить следующее: а/ корректность трансляции концептуальной модели в моделирующую программу, б/ непротиворечивость результатов моделирования тестовых случаев общеизвестным фактам и разумным предположениям.

Корректность трансляции концептуальной модели в моделирующую программу проверена многочисленными пошаговыми /т.е. по тактам/ "трассами" модели, которые показали, что модель работает именно так как и предполагается.

Что касается непротиворечивости результатов моделирования тестовых случаев общеизвестным фактам, укажем сначала на то, что разработанная модель предназначена для анализа относительного влияния различных параметров на производительность МПС. В связи с этим, мы можем отказаться от калибровки модели, так как нас интересуют отношения между результатами, а не их абсолютная величина.

В качестве тестовых случаев, рассматривались прежде всего некоторые "граничные случаи".

Так, например, рассматривалось влияние роста числа процессоров в системе в которой нет кэш-памяти. Результаты показали типичный эффект насыщения, т.е. заметного уменьшения скорости роста эффективной производительности при росте числа процессоров.

Рассматривался и тестовый случай однопроцессорной системы и наблюдалась, замеченная в [95] , обратная логарифмическая зависимость между размером кэш-памяти и числом "промахов", т.е. в нашем случае, производительностью ситемы.

Хотя сравнение результатов моделирования, полученных разрабо-таной моделью с результатами, полученными аналитическими моделями, затруднено сложностью сведения входных параметров к общим характеристикам /это прежде всего относится к способу моделирования поведения программ/, некоторые проявившиеся закономерности получены.; ранее аналитическими моделями.

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

Наконец, нам осталось рассмотреть еще один вопрос, связанный с правильностью моделирования. Это вопрос о длительности моделирования и длительности начального периода установления "стаци°~ нарного" режима работы.

Логически, начальный период длится до момента полного заполнения кэш-памяти. Заметим, однако, что такая ситуация может вообще не возникнуть в зависимости от величины кэш-памяти и характеристик решаемой задачи.

В конкретном случае, длительность, начального периода и периода моделирования определена эвристически, путем тестовых экспериментов Так установлено, что в течении первых 500-800 тактов практически всегда заканчивается специфика, связанная с начальным периодом работы. Так-ше, установлено, что моделирование больше чем 800010000 тактов не имеет никакого влияния на результат моделирования. В связи с этим, практически во всех прогонках модели проводилось моделирование 10000 тактов.

При такой длительности моделирования, каждая прогонка модели заняла, в зависимости от числа значений параметра и аргумента прогонки, от 10 до25 минут машинного времени системы и niv а с 11.00.