Аналитическая модель

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

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

А так как шина памяти медленнее чем процессор, то на одно обращение к памяти уходит несколько Р тактов процессораэто можно посмотреть в BIOS. То есть Чтобы определить коэффициент r общий для всех команд процессора, нужно найти средние значения Tm и Tc по всем командам. Также можно учитывать последствия конвейерной обработки команд, когда чтение данных из памяти для выполнения команды происходит во время выполнения предыдущей команды. Скалярная обработка, когда одновременно выполняется несколько команд, также нужно учесть, как и неравномерное распределение команд в различных программах, зависимость времени доступа к памяти от внешних условий и тд. Но все это невозможно учесть в формуле, нужно строить имитационные модели. 2. Разработать программу, вычисляющую T по формулам и, построить графики. Графики были построены в программе MathCad. Сравнение графиков, построенных по формулам и. Графики разницы между значениями, рассчитанными по формуле и по формуле. 3. Провести эксперименты с программными моделями и сделать выводы насколько применима формула или надо использовать формулу, как используются эти модели для разработки многопроцессорных систем. а Формула применима, так как расхождение между этими формулами небольшое и составляет менее 10. б Эти модели используются, чтобы определить, сколько блоков памяти и какого быстродействия нужно взять при заданном количестве процессоров, при условии достижения оптимальной производительности системы. 4. Преобразовать модели для определения производительности системы в предположении, что 50 обращений ЦП идет к одному блоку памяти, а остальные 50 обращений с равной вероятностью распределены между оставшимися М-1 блоками памяти.

Вероятности выбора блоков памяти равны соответственно Вероятности того, что блоки памяти заблокированы, равны соответственно А вероятности того, что они свободны, равны А для N процессоров соответственно А вероятность того, что память заблокирована Тогда производительность системы с М блоками памяти будет равна TN отношение скорости выполнения команд процессора с учетом конфликтов к скорости без учета конфликтов.

Скорость выполнения команд процессора с учетом конфликтов, а без учета конфликтов Подставив выражение для r в формулу для T получим 5. Преобразовать модели для определения производительности а системы на основе общей шины Для системы на общей шине все блоки памяти можно рассматривать как один, поэтому M1 б системы на основе матричного коммутатора 1.3. Имитационная модель на SMPL Разработать план проведения эксперимента.

Расчет аналитической модели и построение графиков, отражающих результаты моделирования производится в программе MathCad 11.0а. Программа для стохастической имитационной модели реализована на SMPL и транслируется с помощью среды Turbo Pascal 1. Расчеты и графическое оформление производится в программе MathCad 11.0а. Одной из целей данной работы является сопоставление результатов аналитического и имитационного моделирования, представленных в виде графиков.

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

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

Но в аналитической модели мы получали зависимость Т от Mr, где r коэффициент использования памяти в аналитической модели мы приняли r12. Поэтому в случае имитационной модели абсциссой для данного Т является не М, а Мr. В итоге, по результатам каждого прогона имитационной модели для фиксированного N и данного М при r12 получаем на графике точку с координатами Например, в результате прогона имитационной модели для N3, М5 r12 получим следующие результаты Проанализировав результаты, получим по ординате откладываем по абсциссе Таким образом, на графике получили точку с координатами 10 2.715 В результате прогонов имитационной модели для разных М при фиксированном N получим зависимость производительности системы от числа процессоров вернее, от Мr, где r12 в графическом виде, которая пригодна для сопоставления с результатами аналитического моделирования Определить время имитационного моделирования.

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

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

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

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

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

Поэтому при определении оптимального числа блоков памяти и их производительности необходимо учитывать соотношение бюджета разработки и требований к ней. Так, например, из графика для N3 при r12 видно, что при небольшом бюджете и не очень критических требованиях к производительности оптимальным можно назвать число блоков памяти, лежащее в пределах от 4 до 6 Сравнить аналитическую и имитационную модели многопроцессорной системы Построим графики, отражающие результаты аналитического моделирования при помощи приближенной формулы и точной формулы при помощи программы MathCad. По формуле построим графики для N3, N5, N7, N15, N50 и N100 По формуле построим графики для N3, N5, N7 и N15 Аналогично строим графики, отражающие результаты имитационного моделирования при N3, N5, N7 и N15 Здесь и далее yM,N приближенная формула, pj точное значение, qk значения, полученные в результате имитационного моделирования, dh отклонение qk от pj в процентах.

N3 Отклонение от точного значения N5 N7 N15 N50 N100 1.4. Имитационная модель на GPSS Построение модели. параметры модели ProcNum EQU 10 MemNum EQU 4 TimeProc EQU 10 TimeMem EQU 10 переменные Processor VARIABLE 1RN1ProcNum Memory VARIABLE 1ProcNumRN2MemNum GENERATE TimeProcProcNum ASSIGN Proc,VProcessor ASSIGN Mem,VMemory Gate NU PProc QUEUE PMem SEIZE PMem DEPART PMem SEIZE PProc ADVANCE Exponential1,0,TimeProc RELEASE PMem ADVANCE Exponential2,0,TimeProc RELEASE PProc TERMINATE 1 Выбор времени моделирования.

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

Число прогонов модели в нашем случае определяется временем моделирования. Для определения нужного времени моделирования следует сделать несколько пробных прогонов модели.

Сравнить полученные данные и сделать вывод об их достоверности. Наиболее достоверными являются данные, полученные из прогона с максимальным временем моделирования, т.к. в нем собрана наибольшая статистика. Но для нас важно выбрать минимальное время моделирования, при котором данные остаются все еще достоверными. При этом нужно обращать внимание на количество запросов к блокам памяти и на их дисперсию запросов к каждому блоку должно быть не менее 100. Рассмотрим на примере с 10 процессорами и 4 блоками памяти. START 1 START TIME END TIME BLOCKS FACILITIES STORAGES 0.000 4.360 13 6 0 FACILITY ENTRIES UTIL. AVE. TIME AVAIL. OWNER PEND INTER RETRY DELAY 2 1 0.541 2.360 1 2 0 0 0 0 6 1 0.312 1.360 1 3 0 0 1 0 9 1 0.771 3.360 1 0 0 0 0 0 11 1 0.204 0.890 1 0 0 0 0 0 13 1 0.312 1.360 1 3 0 0 0 0 14 1 0.336 1.466 1 0 0 0 0 0 START 100 START TIME END TIME BLOCKS FACILITIES STORAGES 0.000 410.679 13 14 0 FACILITY ENTRIES UTIL. AVE. TIME AVAIL. OWNER PEND INTER RETRY DELAY 1 11 0.502 18.757 1 0 0 0 0 0 2 10 0.473 19.411 1 125 0 0 13 1 3 9 0.231 10.535 1 113 0 0 0 0 4 13 0.554 17.500 1 112 0 0 12 0 5 9 0.316 14.412 1 0 0 0 0 0 6 12 0.588 20.117 1 0 0 0 0 0 7 12 0.501 17.155 1 104 0 0 0 0 8 11 0.456 17.026 1 0 0 0 0 0 9 9 0.324 14.773 1 0 0 0 0 0 10 8 0.480 24.633 1 0 0 0 0 0 11 30 0.931 12.747 1 112 0 0 0 85 12 24 0.978 16.737 1 97 0 0 0 59 13 25 0.993 16.307 1 125 0 0 0 67 14 26 0.989 15.621 1 113 0 0 0 69 START 1000 START TIME END TIME BLOCKS FACILITIES STORAGES 0.000 5150.637 13 14 0 FACILITY ENTRIES UTIL. AVE. TIME AVAIL. OWNER PEND INTER RETRY DELAY 1 108 0.462 22.023 1 0 0 0 8 0 2 94 0.332 18.202 1 1113 0 0 2 1 3 105 0.409 20.080 1 0 0 0 0 0 4 111 0.425 19.741 1 0 0 0 0 0 5 95 0.342 18.535 1 0 0 0 0 0 6 93 0.378 20.908 1 0 0 0 0 0 7 103 0.371 18.530 1 974 0 0 4 0 8 94 0.351 19.235 1 0 0 0 0 0 9 93 0.380 21.053 1 0 0 0 0 0 10 107 0.414 19.933 1 997 0 0 4 0 11 254 0.995 20.167 1 974 0 0 0 1040 12 238 0.998 21.604 1 1008 0 0 0 1011 13 261 0.999 19.723 1 1113 0 0 0 1044 14 251 0.999 20.502 1 997 0 0 0 1033 START 5000 START TIME END TIME BLOCKS FACILITIES STORAGES 0.000 25733.473 13 14 0 FACILITY ENTRIES UTIL. AVE. TIME AVAIL. OWNER PEND INTER RETRY DELAY 1 529 0.401 19.489 1 5145 0 0 3 0 2 485 0.389 20.656 1 0 0 0 0 0 3 486 0.392 20.772 1 4863 0 0 2 0 4 518 0.411 20.401 1 0 0 0 0 0 5 489 0.363 19.098 1 4815 0 0 0 0 6 514 0.413 20.672 1 0 0 0 0 0 7 475 0.354 19.200 1 4810 0 0 3 2 8 514 0.406 20.312 1 0 0 0 0 0 9 492 0.377 19.698 1 0 0 0 0 0 10 503 0.381 19.472 1 5201 0 0 2 0 11 1298 0.999 19.804 1 5163 0 0 0 5146 12 1268 1.000 20.287 1 5206 0 0 0 5078 13 1231 1.000 20.902 1 4863 0 0 0 5180 14 1210 1.000 21.264 1 4815 0 0 0 5312 START 10000 START TIME END TIME BLOCKS FACILITIES STORAGES 0.000 51815.391 13 14 0 FACILITY ENTRIES UTIL. AVE. TIME AVAIL. OWNER PEND INTER RETRY DELAY 1 1004 0.382 19.702 1 0 0 0 0 0 2 984 0.380 19.997 1 0 0 0 0 0 3 997 0.391 20.315 1 0 0 0 0 0 4 1031 0.404 20.289 1 10121 0 0 6 0 5 982 0.370 19.536 1 9569 0 0 7 1 6 1029 0.404 20.327 1 10332 0 0 7 0 7 973 0.365 19.460 1 0 0 0 0 0 8 994 0.383 19.978 1 0 0 0 0 0 9 1006 0.396 20.385 1 10124 0 0 0 0 10 1004 0.388 20.026 1 0 0 0 0 0 11 2526 0.999 20.502 1 10124 0 0 0 10387 12 2549 1.000 20.324 1 10332 0 0 0 10395 13 2453 1.000 21.122 1 9569 0 0 0 10442 14 2477 1.000 20.917 1 9994 0 0 0 10566 START 30000 START TIME END TIME BLOCKS FACILITIES STORAGES 0.000 154018.595 13 14 0 FACILITY ENTRIES UTIL. AVE. TIME AVAIL. OWNER PEND INTER RETRY DELAY 1 2994 0.388 19.954 1 29891 0 0 1 1 2 3002 0.390 19.999 1 0 0 0 0 0 3 2978 0.388 20.074 1 0 0 0 0 0 4 3052 0.395 19.949 1 0 0 0 0 0 5 3016 0.384 19.601 1 0 0 0 0 0 6 3033 0.405 20.548 1 29614 0 0 4 1 7 3013 0.387 19.764 1 0 0 0 0 0 8 2891 0.376 20.046 1 0 0 0 0 0 9 2983 0.389 20.072 1 0 0 0 0 0 10 3040 0.386 19.537 1 0 0 0 0 0 11 7496 1.000 20.543 1 29891 0 0 0 31019 12 7446 1.000 20.684 1 30030 0 0 0 30930 13 7588 1.000 20.297 1 30581 0 0 0 30875 14 7474 1.000 20.607 1 29614 0 0 0 31185 Если посмотреть на столбец ENTRIES, в котором указывается число заявок, поступивших на данное устройство, то мы увидим, что приемлемым временем моделирования будет время 5000 для систем с малым количеством элементов, а лучше брать 10000 для получения более точного результата.

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

План проведения исследований.

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

Т.е. по результатам прогонов имитационной модели на GPSS нам необходимо построить график.

Из каждого прогона мы получаем одну точку графика.

В аналитической модели мы получали зависимость производительности многопроцессорной системыТ от числа блоков памятиМ и их коэффициентов использованияr.

В имитационной модели у нас нет этих данных в явном виде. Производительность системы, соответствующую данному числу блоков памяти М и процессоров, мы можем получить, сложив проценты использования каждого процессора и поделив эту сумму на 100 Т исп1 исп2 испN 100. Процент использования в выходных данных имитационной модели на GPSS обозначается UtilUtility.

Чтобы получить зависимость не просто от М числа блоков памяти, а еще и учесть их коэффициенты использования как это было в аналитической модели, необходимо для каждой точки графика значение М разделить на r в аналитической модели мы брали r 0,5. Таким образом, мы получаем точку, необходимую для построения зависимости Т от Мr. Можно построить и более простую зависимость Т от М без учета r. Покажем построение зависимости Т от Мr по результатам имитационного моделирования на конкретном примере. После проведения имитационного моделирования многопроцессорной системы с 3-мя процессорами и 2-мя блоками памяти мы получили данные следующего вида FACILITYENTRIESUTILAVE. TIME AVAIL.OWNER PEND INTER RETRY DELAY12610,38921,985 1717 00 80 123740,5220,492 10 00 0 033660,50620,385 10 00 0 045180,99628,351 1777 00 0 165654840,99630,335 1717 00 0 1685 Производительность системы вычисляем по формуле, приведенной выше Т исп.1 исп.2 исп. N 100 38,9 52 50,6 100 1,415 Так же вычисляем производительность системы при разных количествах блоков памяти соответственно получаем разные точки графика.

Чтобы эта модель была сравнима с аналитической моделью, нам необходимо учесть коэффициент использования памяти r, которая в аналитической модели была 0,5. Для этого М делим на r, и получаем соответствующую точку на оси абсцисс.

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

Сравнение результатов моделирования сделаем с помощью построения графиков.

Ниже приведены результаты имитационного моделирования после дополнительного преобразования, где Xi число блоков памяти М с учетом их производительности r, Yi производительность системы при таком М, i число процессоров в многопроцессорной системе.

Данные предыдущих моделей.

Данные полученные при моделировании на GPSS Сравнительный график аналитической моделипредставлена двумя формулами R3,0.5 менее точная модель, X3,0.5 более точная модель и 2-х имитационных моделейXg,Yg на GPSS и X,Y - на SMPL для многопроцессорной системы с 3-мя процессорами.

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

Модель можно применять, если определяющим параметром моделирования является не точность модели, а время ее построения. 1.5. Сравнение моделей и их применимость для проектирования В настоящее время широко применяется два вида математического моделирования аналитическое и имитационное.

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

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

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

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

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