СКИПОД ответы на билеты (1127807), страница 9

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

Текст из файла (страница 9)

Потоковая архитектура (data-flow) вычислительных систем обеспечивает интерпретацию алгоритмов на графах, управляемых данными. Идеи потоковой обработки информации, организации вычислений, управляемых потоками данных можно рассмотреть на примере организации ввода и суммирования трех чисел. Традиционная схема вычислений может быть представлена так: ввод (а); ввод (в); ввод (с); s = a+в; s = s+c;

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

ввод (а) ввод (в) ввод (с)

а+в а+с в+с

(в+с)+а (а+с)+в (а+в)+с

Здесь, начальные вершины - ввод, затем каждое введенное данное размножается на три и они передаются на вершины, обеспечивающие суммирование. Теперь, при любом порядке поступления данных отсутствуют задержки вычислений для получения результата. Data-flow программы записываются в терминах графов. В вершинах графа находятся команды, состоящие, например, из оператора, двух операндов (для двуместных операций), возможно, литеральных, или шаблонов для заранее неизвестных данных и ссылки, определяющей команду - наследника и позицию аргумента в ней для результата. Для фрагмента программы, вычисляющего оператор: a=(b+1)*(b-c), команды могут иметь вид:

L1:(+(<b>) "1" L3/1)

L2:(-(<b>) (<c>) L3/2)

L3:(*( ) ( ) <a>)

Семантика выполнения команд следующая: операция команды Li выполняется, когда поступили все данные для их входных аргументов. Последний параметр у этих команд указывает, кому и куда передавать полученные результаты (в примере это узел, команда L3, а - аргументы 1,2), в терминах графов содержит инструкцию для обмена данных.

[править] Реализация потоковых машин.

Основными компонентами потоковой ВС являются:

• память команд (ПК),

• селекторная (арбитражная) сеть,

• множество исполнительных (функциональных) устройств (ФУ),

• распределительная сеть.

_______________

|--------------->| ФУ |-----------------|

| |_____________| |

| |

селекторная сеть распределительная сеть

| ______________ |

|<---------------| ПК |---------------|

|______________|

Память команд состоит из "ячеек" активной памяти, каждая из которых может содержать одну команду вида <метка>: <операция>,<операнд1>,..,<операндК>,<адр_рез1>,..,<адр. _рез.М>, где адреса результатов являются адресами ячеек памяти. С каждой командой связан подсчитывающий элемент, непрерывно ожидающий прибытие аргументов, который пересылает команду на выполнение при наличии полного комплекта аргументов. Активных характер памяти заключается в том, что ячейка, обладающая полным набором операндов, переходит в возбужденное состояние и передает в селекторную сеть информационный пакет, содержащий необходимую числовую и связующую информацию о команде. Селекторная сеть обеспечивает маршрут от каждой командной ячейки к выбранному, в соответствии с кодом операции, исполнительному (функциональному) устройству из множества устройств. Пакет поступает на одно из исполнительных устройств, где соответствующая операция выполняется и результат подается в распределительную сеть. Распределительная сеть обрабатывает результирующий пакет, состоящий из результатов вычислений и адресов назначения. В зависимости от содержимого пакета, результат вычислений поступает в соответствующие ячейки памяти команд, создавая, тем самым, условия возможности их активизации.

Потоковая архитектура (data-flow), как одна из альтернатив фон-Нейманновской, обладает следующими характерными чертами:

• отсутствие памяти как пассивного устройства, хранящего потребляемую информацию,

• отсутствие счетчика команд (и, следовательно, последовательной обработки команд программы, разветвлений по условию и т.д.).

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

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

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

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

4. Языки программирования для потоковых машин существуют, в основном, в виде графических языков машинного уровня. Языки типа SISAL, ориентируемые на описания потоковых алгоритмов, достаточно сложны для программистов.

[править] Нейронные сети как вычислители.

в Википедии

[править] Измерения производительности ЭВМ.

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

• на базе аналитических модели (системами массового обслуживания);

• имитационное моделирование (эмуляция ядерного оружия);

• измерения.

Первый подход обеспечивает наиболее общие и наименее точные ре¬зультаты, последние, наоборот, - наименее общие и наиболее точные. Измерения проводятся контрольными (тестовыми) программами. Бенч-марк (Benchmark) - эталон:

• стандарт, по которому могут быть сделаны измерения или сравнения;

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

Для повышения общности и представительности оценки производительности контрольные программы можно разделить на:

• программы нижнего уровня. Эти программы тестируют основные машинные операции - +,/,* , с учетом времени доступа к памяти, работу кэша, характеристики ввода/вывода.

• ядра программ. Ядра программ - короткие характерные участки программ, например, Ливерморские фортрановские ядра (24 ядра) , Эймсовские ядра НАСА, синтетический тест Ветстоун (Whetstone).

• основные подпрограммы и типовые процедуры; Примером основных подпрограмм могут быть программы Линпак (Linpack) , программы типа быстрого преобразования Фурье. Программа Линпак - процедура решения системы линейных уравнений методом исключения Гаусса. В этой схеме вычислений точно известно число операций с плавающей точкой, которое зависит от размерности массивов – параметров. Стандартные значения размерностей 100 или 1000. Для параллельных ЭВМ имеется соответствующая версия теста.

• полные основные прикладные программы; В качестве примеров программ этого уровня приводятся Лос-Аламосские тестовые программы моделирования поведения плазмы и программы гидродинамики.

• перспективные прикладные программы.

[править] Реальная и полная производительность вычислителей.

Оценка производительности вычислительных систем имеет два аспекта:

• оценка пиковой производительности – номинального быстродействия системы

• получение оценок максимальной - “реальной” производительности.

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

Для оценки производительности вычислительных систем в ТОР500 используются обозначения Rpeak – пиковая, предельная производительность и Rmax – максимальная производительность при решении задачи Linpack.

Наиболее абстрактной единицей измерения производительности микропроцессоров является тактовая частота ПК, частота тактового генератора (clock rate,). Любая операция в процессоре не может быть выполнена быстрее, чем за один такт (период) генератора. Итак, минимальное время исполнения одной логической операции (переключение транзистора) - один такт. Тактовая частота измеряется в Герцах – число тактов в секунду.

Другой обобщенной мерой производительности ПК может служить число команд, выполняемых в единицу времени. Для вычислителей фон-Нейманновской архитектуры скорость выполнения команд уже может быть параметром, который может быть использован для оценки времени выполнения программы. Этот параметр - MIPS (Million Instruction Per Second)- миллион операций (команд, инструкций ЭВМ)/сек. Так как время выполнения различных команд может различаться, то данных параметр сопровождался разного вида уточнениями (логических команд, заданной смеси команд и т.д.), а также наиболее известной здесь мерой в 1 MIPS – это производительность вычислителя VAX 11/780. Итак, данный параметр также достаточно условен.

Так как для большинства вычислительных алгоритмов существуют оценки числа арифметических операций, необходимых для выполнения расчетов, данная мера и может служить тем показателем, который и интересует пользователей в первую очередь. Это – MFLPOPS (Million of Floating point Operation Per Second – Мегафлопс)- миллион операций на данных с плавающей запятой/сек, единица быстродействия ЭВМ в операциях с плавающей запятой, есть также единицы - GFLPOPS и ТFLPOPS (терафлопс = 10**12 оп./сек.).

[править] Пакеты для измерения производительности вычислительных систем.

[править] LINPACK

Linpack — программная библиотека, написанная на языке Фортран, которая содержит набор подпрограмм для решения систем линейных алгебраических уравнений.

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

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

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

[править] SPEC-89

оффсайт

Standard Performance Evaluation Corporation -- non-profit, industry-sponsored organization

Three main SPEC versions

• SPEC89

• SPECint92/SPECfp92

• SPEC95 Base/Peak int/fp

• SPEC CPU 2000

SPEC 89:

• Integer and floating point combined

• Normalized to a VAX-11/780 (VUP)

• Geometric mean of individual relative times

• Ad-hoc collection, many programs small enough to be cached

[править] Параметры рейтинга ТОР500.

TOP 500

• Номер в списке

• Производитель

• Computer - Type indicated by manufacturer or vendor

• Installation Site - Customer

• Страна

• Год последнего обновления информации о системе

• Field of Application

• Количество процессоров

• Rmax - максиальная производительность, достигнутая на тесте LINPACK

• Rpeak - теоретическая пиковая производительность

• Nmax - Problem size for achieving Rmax

• N1/2 - Problem size for achieving half of Rmax

[править] Закон Амдала.

Закон Амдала показывает коэффициент ускорения выполнения программы на параллельных системах в зависимости от степени распараллеливания программы. Пусть: N - число процессоров системы, P - доля распараллеливаемой части программы, а S = 1-P - доля скалярных операций программы, выполняемых без совмещения по времени.( S+P = 1 , S,P >= 0). Тогда, по Амдалу, общее время выполнения программы на однопроцессорном вычислителе S+P, на мультипроцессоре: S+P/N, а ускорение при этом есть функция от P: Sp = (S+P)/(S+P/N) = 1/(S+P/N).

Из формулы закона Амдала следует,что при:

P = 0 S = 1 - ускорения вычисления нет, а

P = 1 S = 0 - ускорение вычислений в N раз

Если P = S = 0.5, то даже при бесконечном числе процессоров уско­рение не может быть более чем в 2 раза.

[править] Параллельные алгоритмы. Метрики.

[править] DOP (Degree Of Parallelism)

Степень параллелизма программы – D(t) – число процессоров, участвующих в исполнении программы в момент времени t. DOP зависит от алгоритма программы, эффективности компиляции и доступных ресурсов при исполнении. График D(t) – профиль параллелизма программы.

[править] Speedup

• T(n) – время исполнения программы на n процессорах

• T(n)<T(1), если параллельная версия алгоритма эффективна

• T(n)>T(1), если накладные расходы (издержки) реализации параллельной версии алгоритма чрезмерно велики

Ускорение за счёт параллельного выполнения S(n) = T(1) / T(n)

[править] Efficiency

Эффективность системы из n процессоров E(n) = S(n) / n

• Случай S(n)=n – линейное ускорение – масштабируемость (Scalability) алгоритма (возможность ускорения вычислений пропорционально числу процессоров)

• Случай S(n)>n – суперлинейное ускорение (например, из-за большего коэффициента кеш-попаданий)

[править] Параллельные алгоритмы редукции.

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

Данные А1 А2 А3 А4 А5 А6 А7 А8

Характеристики

Список файлов ответов (шпаргалок)