Редактирование: ПОД (3 поток), Ответы

Материал из eSyr's wiki.

Перейти к: навигация, поиск

Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.

ПРЕДУПРЕЖДЕНИЕ: Длина этой страницы составляет 318 килобайт. Страницы, размер которых приближается к 32 КБ или превышает это значение, могут неверно отображаться в некоторых браузерах. Пожалуйста, рассмотрите вариант разбиения страницы на меньшие части.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.

Текущая версия Ваш текст
Строка 84: Строка 84:
===Первое поколение===
===Первое поколение===
-
Первое поколение ЭВМ /1946-1957гг/ использовало в качестве основного элемента электронную лампу. Быстродействие их не превышало 2-3 т. оп./сек; емкость ОЗУ - 2-4 К слов. Это ЭВМ: БЭСМ-1 (В.А. Мельников,1955г.), Минск-1 (И.С. Брук 1952/59 гг.), Урал-4 (Б. И. Рамеев), Стрела (Ю.Я. Базилевский, 1953 г.), М-20 (М.К. Сулим 1860 г. <!-- Парень явно опередил своё время! -->). А.Н. Мямлиным была разработана и несколько лет успешно эксплуатировалась "самая большая в мире ЭВМ этого поколения" <!-- Ох уж эти советские микросхемы, самые большие микросхемы в мире! -->- машина Восток. Программирование для этих машин: однозадачный, пакетный режим, машинный язык, ассемблер (советский аналог - [[wikipedia:ru:Автокод#Происхождение и критика термина «язык ассемблера»|Автокод]]).
+
Первое поколение ЭВМ /1946-1957гг/ использовало в качестве основного элемента электронную лампу. Быстродействие их не превышало 2-3 т. оп./сек; емкость ОЗУ - 2-4 К слов. Это ЭВМ: БЭСМ-1 (В.А. Мельников,1955г.), Минск-1 (И.С. Брук 1952/59 гг.), Урал-4 (Б. И. Рамеев), Стрела (Ю.Я. Базилевский, 1953 г.), М-20 (М.К. Сулим 1860 г. <!-- Парень явно опередил своё время! -->). А.Н. Мямлиным была разработана и несколько лет успешно эксплуатировалась "самая большая в мире ЭВМ этого поколения" <!-- Ох уж эти советские микросхемы, самые большие микросхемы в мире! -->- машина Восток. Программирование для этих машин: однозадачный, пакетный режим, машинный язык, ассемблер (совковый аналог - [[wikipedia:ru:Автокод#Происхождение и критика термина «язык ассемблера»|Автокод]]).
===Второе поколение===
===Второе поколение===
Строка 127: Строка 127:
===Принцип однородности памяти.===
===Принцип однородности памяти.===
-
Программы и данные хранятся в одной и той же памяти в двоичной системе счисления (иногда выделяют '''принцип двоичного представления данных'''). Поэтому компьютер не различает, что хранится в данной ячейке памяти — число, текст или команда. Над командами можно выполнять такие же действия, как и над данными. Это открывает целый ряд возможностей. Например, программа в процессе своего выполнения также может подвергаться переработке, что позволяет задавать в самой программе правила получения некоторых ее частей (так в программе организуется выполнение циклов и подпрограмм). Более того, команды одной программы могут быть получены как результаты исполнения другой программы. На этом принципе основаны методы трансляции — перевода текста программы с языка программирования высокого уровня на язык конкретной машины.
+
Программы и данные хранятся в одной и той же памяти s двоичной системе счисления (иногда выделяют '''принцип двоичного представления данных'''). Поэтому компьютер не различает, что хранится в данной ячейке памяти — число, текст или команда. Над командами можно выполнять такие же действия, как и над данными. Это открывает целый ряд возможностей. Например, программа в процессе своего выполнения также может подвергаться переработке, что позволяет задавать в самой программе правила получения некоторых ее частей (так в программе организуется выполнение циклов и подпрограмм). Более того, команды одной программы могут быть получены как результаты исполнения другой программы. На этом принципе основаны методы трансляции — перевода текста программы с языка программирования высокого уровня на язык конкретной машины.
===Принцип адресности.===
===Принцип адресности.===
Строка 136: Строка 136:
У лектора немного другая структура принципов.
У лектора немного другая структура принципов.
=== Программное управление работой ЭВМ ===
=== Программное управление работой ЭВМ ===
-
Программа -- последовательность команд, хранимая в ОЗУ. Каждая программа задает единичный акт преобразования информации. В каждый момент времени выполняется только 1 команда программы.
+
Программа -- последовательность комманд, хранимая в ОЗУ. Каждая программа задает единичный акт преобразования информации. В каждый момент времени выполняется только 1 команда программы.
-
 
+
=== Принцип условного перехода ===
=== Принцип условного перехода ===
-
Возможен переход в процессе вычисления на тот или иной участок программы в зависимости от промежуточных, получаемых в ходе вычисления, результатов.
+
Возможен переход в процессе вычисления на тот или иной участок программы в зависимости от промежуточных, получаемых а ходе вычисления, результатов.
-
 
+
=== Принцип хранимой программы ===
=== Принцип хранимой программы ===
-
Команды представляются в числовой форме и хранятся в ОЗУ, в том же виде, что и исходные данные, следовательно над командой можно производить арифметические действия, изменяя ее динамически.
+
Команды представляются в числовой форме и хранятся в ОЗУ, в том же виде, что и исходные данные, следовательно над командо йможно производить арифметические действия, изменяя ее динамически.
-
 
+
=== Принцип использования двоичной системы счисления для представления информации ===
=== Принцип использования двоичной системы счисления для представления информации ===
Строка 171: Строка 168:
В устройствах прямого доступа для того, чтобы прочесть i-ый блок данных, не нужно читать первые i-1 блоков данных. (Пример: пульт дистанционного управления Вашего телевизора, кнопки - каналы; для того, чтобы посмотреть i-ый канал не нужно «перещелкивать» первые i-1).
В устройствах прямого доступа для того, чтобы прочесть i-ый блок данных, не нужно читать первые i-1 блоков данных. (Пример: пульт дистанционного управления Вашего телевизора, кнопки - каналы; для того, чтобы посмотреть i-ый канал не нужно «перещелкивать» первые i-1).
*'''Магнитные диски'''. Конструкция ВЗУ данного типа состоит в том, что имеется несколько дисков (компьютерный жаргон - «блины»), обладающих возможностью с помощью эффекта перемагничивания хранить информацию, размещенных на оси, которые вращаются с некоторой постоянной скоростью. Каждый такой диск имеет одну или две поверхности, покрытые слоем, позволяющим записывать информацию
*'''Магнитные диски'''. Конструкция ВЗУ данного типа состоит в том, что имеется несколько дисков (компьютерный жаргон - «блины»), обладающих возможностью с помощью эффекта перемагничивания хранить информацию, размещенных на оси, которые вращаются с некоторой постоянной скоростью. Каждый такой диск имеет одну или две поверхности, покрытые слоем, позволяющим записывать информацию
-
*'''Магнитный барабан'''. Металлический цилиндр большой массы, вращающийся вокруг своей оси. Роль большой массы - поддержание стабильной скорости вращения. Поверхность этого цилиндра покрыта магнитным слоем, позволяющим хранить, читать и записывать информацию. Поверхность барабана разделена на n равных частей (в виде колец), которые называются треками (track). Над барабаном расположен блок неподвижных головок так, что над каждым треком расположена одна и только одна головка. (Головок, соответственно, тоже n штук). Головки способны считывать и записывать информацию с барабана. Каждый трек разделен на равные сектора. В каждый момент времени в устройстве может работать только одна головка. Запись информации происходит по трекам барабана, начиная с определенного сектора. При заказе на обмен поступают следующие параметры: № трека, № сектора, объем информации.
+
*'''Магнитный барабан'''.металлический цилиндр большой массы, вращающийся вокруг своей оси. Роль большой массы - поддержание стабильной скорости вращения. Поверхность этого цилиндра покрыта магнитным слоем, позволяющим хранить, читать и записывать информацию. Поверхность барабана разделена на n равных частей (в виде колец), которые называются треками (track). Над барабаном расположен блок неподвижных головок так, что над каждым треком расположена одна и только одна головка. (Головок, соответственно, тоже n штук). Головки способны считывать и записывать информацию с барабана. Каждый трек разделен на равные сектора. В каждый момент времени в устройстве может работать только одна головка. Запись информации происходит по трекам барабана, начиная с определенного сектора. При заказе на обмен поступают следующие параметры: № трека, № сектора, объем информации.
*''' Магнито-электронные ВЗУ прямого доступа (память на магнитных доменах)'''. В конструкции этого устройства опять-таки используется барабан, но на этот раз он неподвижен. Барабан опять-таки разделен на треки и над каждым треком имеется своя головка. За счет некоторых магнитно-электрических эффектов происходит перемещение по треку цепочки доменов. При этом каждый домен однозначно ориентирован, то есть он бежит стороной, с зарядом «+», либо стороной, заряженной «-». Так кодируется ноль и единица. Эта память очень быстродейственна, т.к. в ней нет «механики». Память на магнитных доменах очень дорога и используется в большинстве случаев в военной и космической областях.
*''' Магнито-электронные ВЗУ прямого доступа (память на магнитных доменах)'''. В конструкции этого устройства опять-таки используется барабан, но на этот раз он неподвижен. Барабан опять-таки разделен на треки и над каждым треком имеется своя головка. За счет некоторых магнитно-электрических эффектов происходит перемещение по треку цепочки доменов. При этом каждый домен однозначно ориентирован, то есть он бежит стороной, с зарядом «+», либо стороной, заряженной «-». Так кодируется ноль и единица. Эта память очень быстродейственна, т.к. в ней нет «механики». Память на магнитных доменах очень дорога и используется в большинстве случаев в военной и космической областях.
Строка 213: Строка 210:
= Ассоциативная память. =
= Ассоциативная память. =
-
Оперативную память (ОП) можно представить в виде двумерной таблицы, строки которой хранят в двоичном коде команды и данные. Обращения за содержимым строки производится заданием номера (адреса) нужной строки. При записи, кроме адреса строки указывается регистр, содержимое которого следует записать в эту строку. Запись занимает больше времени, чем чтение. Пусть в памяти из трех строк хранятся номера телефонов.
+
Оперативную память (ОП) можно представить в виде двумерной таблицы, строки которой хранят в двоичном коде команды и данные. Обращения за содержимом строки производится заданием номера (адреса) нужной строки. При записи, кроме адреса строки указывается регистр, содержимое которого следует записать в эту строку. Запись занимает больше времени, чем чтение. Пусть в памяти из трех строк хранятся номера телефонов.
{| border=1
{| border=1
Строка 264: Строка 261:
'''Ответ:''' Область памяти делим ровно пополам. Первая половина заполняется ключами, вторая соответствующими ключам значениями. Когда найден ключ, известен его адрес как смещение относительно начала памяти. Тогда адрес содержимого по ключу – это смещение + размер области ключей, то есть адрес ячейки из второй половины памяти, которая соответствует ключу. ''А не имеется ли тут в виду реализация hash или индексных деревьев?''
'''Ответ:''' Область памяти делим ровно пополам. Первая половина заполняется ключами, вторая соответствующими ключам значениями. Когда найден ключ, известен его адрес как смещение относительно начала памяти. Тогда адрес содержимого по ключу – это смещение + размер области ключей, то есть адрес ячейки из второй половины памяти, которая соответствует ключу. ''А не имеется ли тут в виду реализация hash или индексных деревьев?''
- 
-
'''Ответ-2''': Предположим, у нас очень много оперативной памяти. Тогда рассмотрим ключ, как двоичную последовательность, то есть, это некое число. Рассмотрим это число, как адрес в памяти - там и будем хранить и искать значение, соответствующее данному ключу.
 
= Виртуальная память. =
= Виртуальная память. =
Внутри программы к моменту образования исполняемого модуля используется модель организации адресного пространства программы (эта модель, в общем случае не связана с теми ресурсами ОЗУ, которые предполагается использовать позднее). Для простоты будем считать, что данная модель представляет собой непрерывный фрагмент адресного пространства в пределах которого размещены данные и команды программы. Будем называть подобную организацию адресации в программе программной адресацией или '''логической/виртуальной адресацией'''.
Внутри программы к моменту образования исполняемого модуля используется модель организации адресного пространства программы (эта модель, в общем случае не связана с теми ресурсами ОЗУ, которые предполагается использовать позднее). Для простоты будем считать, что данная модель представляет собой непрерывный фрагмент адресного пространства в пределах которого размещены данные и команды программы. Будем называть подобную организацию адресации в программе программной адресацией или '''логической/виртуальной адресацией'''.
-
Итак, повторяем, на уровне исполняемого кода имеется программа в машинных кодах, использующая адреса данных и команд. Эти адреса в общем случае не являются адресами конкретных физических ячеек памяти, в которых размещены эти данные, более того, впоследствии мы увидим, что виртуальным (или программным) адресам могут ставиться в соответствие произвольные физические адреса памяти. То есть при реальном исполнении программы далеко не всегда виртуальная адресация, используемая в программе совпадает с физической адресацией, используемой ЦП при выполнении данной программы.
+
Итак, повторяем, на уровне исполняемого кода имеется программа в машинных кодах, использующая адреса данных и команд. Эти адреса в общем случае не являются адресами конкретных физических ячеек памяти, в которых размещены эти данные, более того, в последствии мы увидим, что виртуальным (или программным) адресам могут ставиться в соответствие произвольные физические адреса памяти. То есть при реальном исполнении программы далеко не всегда виртуальная адресация, используемая в программе совпадает с физической адресацией, используемой ЦП при выполнении данной программы.
===Базирование адресов.===
===Базирование адресов.===
Строка 331: Строка 326:
===Алгоритм «Часы»===
===Алгоритм «Часы»===
-
''(Это то же самое, что и алгоритм вторая попытка)''
 
#Если R=0, то выгрузка страницы и стрелка на позицию вправо.
#Если R=0, то выгрузка страницы и стрелка на позицию вправо.
#Если R=1, то R-обнуляется, стрелка на позицию вправо и на П.1.
#Если R=1, то R-обнуляется, стрелка на позицию вправо и на П.1.
Строка 341: Строка 335:
* Памяти N страниц. Существует битовая матрица NxN (изначально полностью обнулена).
* Памяти N страниц. Существует битовая матрица NxN (изначально полностью обнулена).
* При каждом обращении к i-ой странице происходит присваивание 1 всем битам i-ой строки и 0 - всем битам i-ого столбца.
* При каждом обращении к i-ой странице происходит присваивание 1 всем битам i-ой строки и 0 - всем битам i-ого столбца.
-
* Строка с наименьшим числом единиц - искомая
+
* Строка с наименьшим двоичным кодом - искомая
-
 
+
===Алгоритм NFU===
===Алгоритм NFU===
Not Frequently Used – редко использовавшаяся страница (Программная модификация LRU (?))
Not Frequently Used – редко использовавшаяся страница (Программная модификация LRU (?))
Строка 407: Строка 401:
'''Writethrough'''
'''Writethrough'''
-
При обновлении кэш-памяти методом сквозной записи контроллер кэш-памяти одновременно обновляет содержимое основной памяти. Иначе говоря, основная память отражает текущее содержимое кэш-памяти. Быстрое обновление позволяет перезаписывать любой блок в кэш-памяти в любое время без потери данных. Система со сквозной записью проста, но время, требуемое для записи в основную память, снижает производительность и увеличивает количество обращений по шине (что особенно заметно в мультизадачной системе).
+
При обновлении кэш-памяти методом сквозной записи контроллер кэш-памяти одновременно обновляет содержимое основной памяти. Иначе говоря, основная память отражает текущее содержимое кэш-памяти. Быстрое обновление позволяет перезаписывать любой блок в кэш-памяти в любое время без потери данных. Система со сквозной записью проста, но время, требуемое для записи в основную память, снижает производительность и увеличивает количество обращений по шине (что особенно заметно с мультизадачной системе).
'''Буферизованная сквозная запись.'''
'''Буферизованная сквозная запись.'''
Строка 433: Строка 427:
В современных компьютерах многоуровневая структура кэша, которая позволяет очень быстро выполнять обход массива. Попадание кэша настолько быстрая операция, что можно учитывать только промахи. Если строка кэша имеет размер B, то колличество промахов в массиве равно n/B. Если рассматривать связный список, то в худшем случае на доступ к каждому узлу будет приходится промах. Но даже в лучшем случае, когда узлы списка расположенны последовательно, из-за того, что узел у списка больше, может потребоваться в несколько раз больше кэша для прохода по списку.
В современных компьютерах многоуровневая структура кэша, которая позволяет очень быстро выполнять обход массива. Попадание кэша настолько быстрая операция, что можно учитывать только промахи. Если строка кэша имеет размер B, то колличество промахов в массиве равно n/B. Если рассматривать связный список, то в худшем случае на доступ к каждому узлу будет приходится промах. Но даже в лучшем случае, когда узлы списка расположенны последовательно, из-за того, что узел у списка больше, может потребоваться в несколько раз больше кэша для прохода по списку.
-
Пусть у нас есть массив из 60 миллионов элементов и мы хотим вставить элементы в середину. Несмотря на преимущества, которые дает кэш, эта операция займет недели (Какого размера должны быть элементы чтобы копирование 30 миллионов элементов заняло недели? Секунды, ну максимум минуты...).
+
Пусть у нас есть массив из 60 миллионов элементов и мы хотим вставить элементы в середину. Несмотря на преимущества, которые дает кэш, эта операция займет недели.
Поэтому в программах, где вставка и удаление элементов является частой операцией, массивы неприменимы. Также недостатком массивов явлеется то, что они медленно увеличиваются и фрагментируют память.
Поэтому в программах, где вставка и удаление элементов является частой операцией, массивы неприменимы. Также недостатком массивов явлеется то, что они медленно увеличиваются и фрагментируют память.
Строка 439: Строка 433:
Такой структурой будет связный список маленьких массивов. А, чтобы эту структуру сделать cache-aware, нужно, чтобы каждый узел такого связного списка был размером B (т.е. размером со строку кэша).
Такой структурой будет связный список маленьких массивов. А, чтобы эту структуру сделать cache-aware, нужно, чтобы каждый узел такого связного списка был размером B (т.е. размером со строку кэша).
- 
-
(Комментарий от Жукова В.В.: Пусть у нас есть список, элементы которого это int'ы. Объединяем их в массивы, например по 8192 штуки (размер int'a - 4 байта, 4 * 8192 = 32768 байт - размер L1-кэша на текущей машине). Например, мы захотели вставить один int в самое начало списка. Тогда нам придётся сдвигать весь первый массив на одну позицию, затем вставлять последний элемент этого массива в начало второго, проделать ту же процедуру со вторым массивом и т.д. В итоге получаем, что нам придётся пройти по всем массивам списка и перезаписать значения в элементах этого массива. Даже обычный длинный массив будет лучше, чем это: во-первых, при прохождении по массиву у нас всё-равно он кэшируется, во-вторых он лежит в последовательном участке памяти, в отличие от предложенных нескольких маленьких массивов, которые находятся в разных местах ОП, в-третьих нам не нужно разыменовывать указатель для перехода к следующему блоку, в-четвёртых, код алгоритма работы с одним массивом будет значительно короче. В общем, плохой пример.)
 
=== Оптимизация сортировки слиянием ===
=== Оптимизация сортировки слиянием ===
Строка 547: Строка 539:
* Сформировать исполнительный адрес
* Сформировать исполнительный адрес
* Выбрать операнды
* Выбрать операнды
-
* Выполнить команду
+
* Выполнить комманду
* Записать результат
* Записать результат
Строка 763: Строка 755:
= Метакомпъютинг. =
= Метакомпъютинг. =
-
GRID-сети — это совокупность вычислительных систем, связанных через Интернет (метакомпьютинг). Используются для решения задач, допускающих сегментацию на независимые вычислительные процессы с большим объемом вычислений. Такими задачами являются задача исследования генома, обработку результатов физических испытаний, проект SETI.
+
GRID-сети это совокупность вычислительных систем, связанных через Интернет (метакомпьютинг). Используются для решения задач, допускающих сегментацию на независимые вычислительные процессы с большим объемом вычислений. Такими задачами являются задача исследования генома, обработку результатов физических испытаний, проект CETI.
Основная схема работы в этом случае примерно такая: специальный агент, расположенный на вычислительном узле (компьютере пользователя), определяет факт простоя этого компьютера, соединяется с управляющим узлом метакомпьютера и получает от него очередную порцию работы (область в пространстве перебора). По окончании счета по данной порции вычислительный узел передает обратно отчет о фактически проделанном переборе или сигнал о достижении цели поиска.
Основная схема работы в этом случае примерно такая: специальный агент, расположенный на вычислительном узле (компьютере пользователя), определяет факт простоя этого компьютера, соединяется с управляющим узлом метакомпьютера и получает от него очередную порцию работы (область в пространстве перебора). По окончании счета по данной порции вычислительный узел передает обратно отчет о фактически проделанном переборе или сигнал о достижении цели поиска.
Строка 807: Строка 799:
= Симметричные мультипроцессоры. =
= Симметричные мультипроцессоры. =
-
Системы данного класса: SMP (Scalable Parallel Processor, ''может всё же Symmetric Multiprocessing?'') состоят из нескольких однородных процессоров и массива общей памяти (разделяемой памяти – shared memory): любой процессор может обращаться к любому элементу памяти. По этой схеме построены 2,4 процессорные SMP сервера на базе процессоров Intel, НР и т. д., причем процессоры подключены к памяти с помощью общей шины. Системы с большим числом процессоров (но не более 32) подключаются к общей памяти, разделенной на блоки, через не блокирующийся полный коммутатор: crossbar. Любой процессор системы получает данное по произвольному адресу памяти за одинаковое время, такая структура памяти называется: UMA - Uniform Memory Access (Architecture). Пример:НР-9000. Дальнейшее масштабирование (увеличение числа процессоров системы) SMP систем обеспечивается переходом к архитектуре памяти: NUMA - Nоn Uniform Memory Access. По схеме, называемой, этой иногда, кластеризацией SMP, соответствующие блоки памяти двух (или более) серверов соединяются кольцевой связью, обычно по GCI интерфейсу. При запросе данного, расположенного вне локального с сервере диапазона адресов, это данное по кольцевой связи переписывается дублируется в соответствующий блок локальной памяти, ту часть его, которая специально отводится для буферизации глобальных данных и из этого буфера поставляется потребителю. Эта буферизация прозрачна (невидима) пользователю, для которого вся память кластера имеет сквозную нумерацию, и время выборки данных, не локальных в сервере, будет равно времени выборки локальных данных при повторных обращениях к глобальному данному, когда оно уже переписано в буфер. Данный аппарат буферизации есть типичная схема кэш памяти. Так как к данным возможно обращение из любого процессора кластера, то буферизация, размножение данных требует обеспечение их когерентности. Когерентность данных состоит в том, что при изменении данного все его потребители должны получать это значение. Проблема когерентности усложняется дублированием данных еще и в процессорных кэшах системы. Системы, в которых обеспечена когерентность данных, буферизуемых в кэшах, называются кэш когерентными (cc-cache coherent), а архитектура памяти описываемого кластера: cc- NUMA (cache coherent Nоn Uniform Memory Access). Классической архитектурой принято считать систему SPP1000.
+
Системы данного класса: SMP (Scalable Parallel Processor) состоят из нескольких однородных процессоров и массива общей памяти (разделяемой памяти – shared memory): любой процессор может обращаться к любому элементу памяти. По этой схеме построены 2,4 процессорные SMP сервера на базе процессоров Intel, НР и т. д., причем процессоры подключены к памяти с помощью общей шины. Системы с большим числом процессоров (но не более 32) подключаются к общей памяти, разделенной на блоки, через не блокирующийся полный коммутатор: crossbar. Любой процессор системы получает данное по произвольному адресу памяти за одинаковое время, такая структура памяти называется: UMA - Uniform Memory Access (Architecture). Пример:НР-9000. Дальнейшее масштабирование (увеличение числа процессоров системы) SMP систем обеспечивается переходом к архитектуре памяти: NUMA - Nоn Uniform Memory Access. По схеме, называемой, этой иногда, кластеризацией SMP, соответствующие блоки памяти двух (или более) серверов соединяются кольцевой связью, обычно по GCI интерфейсу. При запросе данного, расположенного вне локального с сервере диапазона адресов, это данное по кольцевой связи переписывается дублируется в соответствующий блок локальной памяти, ту часть его, которая специально отводится для буферизации глобальных данных и из этого буфера поставляется потребителю. Эта буферизация прозрачна (невидима) пользователю, для которого вся память кластера имеет сквозную нумерацию, и время выборки данных, не локальных в сервере, будет равно времени выборки локальных данных при повторных обращениях к глобальному данному, когда оно уже переписано в буфер. Данный аппарат буферизации есть типичная схема кэш памяти. Так как к данным возможно обращение из любого процессора кластера, то буферизация, размножение данных требует обеспечение их когерентности. Когерентность данных состоит в том, что при изменении данного все его потребители должны получать это значение. Проблема когерентности усложняется дублированием данных еще и в процессорных кэшах системы. Системы, в которых обеспечена когерентность данных, буферизуемых в кэшах, называются кэш когерентными (cc-cache coherent), а архитектура памяти описываемого кластера: cc- NUMA (cache coherent Nоn Uniform Memory Access). Классической архитектурой принято считать систему SPP1000.
= Архитектура памяти cc-NUMA. =
= Архитектура памяти cc-NUMA. =
Строка 829: Строка 821:
= Парадигмы программирования для параллельных вычислителей. =
= Парадигмы программирования для параллельных вычислителей. =
-
* '''Модель Передачи сообщений'''. В этой модели процессы независимы и имеют собственное адресное пространство. Основной способ взаимодействия и синхронизации – передача сообщений. Стандарт интерфейса передачи сообщений является MPI.
+
* Модель Передачи сообщений. В этой модели процессы независимы и имеют собственное адресное пространство. Основной способ взаимодействия и синхронизации – передача сообщений. Стандарт интерфейса передачи сообщений является MPI.
-
* '''Модель с общей памятью'''. В этой модели процессы имеют единое адресное пространство. Доступ к общим данным регламентируется с помощью примитивов синхронизации. Стандартом для моделей с общей памятью является OpenMP.
+
* Модель с общей памятью. В этой модели процессы имеют единое адресное пространство. Доступ к общим данным регламентируется с помощью примитивов синхронизации. Стандартом для моделей с общей памятью является OpenMP.
-
* '''Модель параллелизма по данным'''. В этой модели данные разделяются между узлами вычислительной системы , а последовательная программа их обработки преобразуется компилятором либо в модель передачи сообщений, либо в модель с общей памятью. При этом вычисления распределяются по правилу собственных вычислений: каждый процессор выполняет вычисление данных, распределенных на него. Примерами могут являться стандарты HPF1 HPF2. На модели параллелизма по данным была разработана отечественная система DVM.
+
* Модель параллелизма по данным. В этой модели данные разделяются между узлами вычислительной системы , а последовательная программа их обработки преобразуется компилятором либо в модель передачи сообщений, либо в модель с общей памятью. При этом вычисления распределяются по правилу собственных вычислений: каждый процессор выполняет вычисление данных, распределенных на него. Примерами могут являться стандарты HPF1 HPF2. На модели параллелизма по данным была разработана отечественная система DVM.
= Нетрадиционные вычислители. =
= Нетрадиционные вычислители. =
Строка 916: Строка 908:
# Обработка векторных регулярных структур через механизмы потока данных менее эффективна, чем традиционные решения.
# Обработка векторных регулярных структур через механизмы потока данных менее эффективна, чем традиционные решения.
# Языки программирования для потоковых машин существуют, в основном, в виде графических языков машинного уровня. Языки типа SISAL, ориентируемые на описания потоковых алгоритмов, достаточно сложны для программистов.
# Языки программирования для потоковых машин существуют, в основном, в виде графических языков машинного уровня. Языки типа SISAL, ориентируемые на описания потоковых алгоритмов, достаточно сложны для программистов.
- 
-
Для тех, кто тоже не понял этот поток сознания: статья на Хабрахабре [http://habrahabr.ru/post/122479/ «Dataflow-архитектуры. Часть 1»].
 
= Нейронные сети как вычислители. =
= Нейронные сети как вычислители. =
-
[[wikipedia:ru:Нейрокомпьютер|в Википедии]]
+
[[wikipedia:ru:Искусственная нейронная сеть|в Википедии]]
= Измерения производительности ЭВМ. =
= Измерения производительности ЭВМ. =
Обычно, рассматриваются три подхода к оценке производительности:
Обычно, рассматриваются три подхода к оценке производительности:
* на базе аналитических модели (системами массового обслуживания);
* на базе аналитических модели (системами массового обслуживания);
-
* имитационное моделирование (эмуляция ядерного оружия);
+
* имитационное моделирование;
* измерения.
* измерения.
Строка 940: Строка 930:
= Реальная и полная производительность вычислителей. =
= Реальная и полная производительность вычислителей. =
-
Оценка производительности вычислительных систем имеет два аспекта:
+
Оценка производительности вычислительных систем имеет два аспекта: оценка пиковой производительности – номинального быстродействия системы и получение оценок максимальной - “реальной” производительности. Если номинальная(пиковая, предельная) оценка однозначно определяется техническими параметрами оборудования, то вторая характеристика указывает производительность системы в реальной среде применения. Для оценки производительности вычислительных систем в ТОР500 используются обозначения Rpeak – пиковая, предельная производительность и Rmax – максимальная производительность при решении задачи Linpack.
-
* оценка пиковой производительности – номинального быстродействия системы
+
-
* получение оценок максимальной - “реальной” производительности.
+
-
 
+
-
Если номинальная(пиковая, предельная) оценка однозначно определяется техническими параметрами оборудования, то вторая характеристика указывает производительность системы в реальной среде применения.
+
-
 
+
-
Для оценки производительности вычислительных систем в ТОР500 используются обозначения Rpeak – пиковая, предельная производительность и Rmax – максимальная производительность при решении задачи Linpack.
+
-
 
+
Наиболее абстрактной единицей измерения производительности микропроцессоров является тактовая частота ПК, частота тактового генератора (clock rate,). Любая операция в процессоре не может быть выполнена быстрее, чем за один такт (период) генератора. Итак, минимальное время исполнения одной логической операции (переключение транзистора) - один такт. Тактовая частота измеряется в Герцах – число тактов в секунду.
Наиболее абстрактной единицей измерения производительности микропроцессоров является тактовая частота ПК, частота тактового генератора (clock rate,). Любая операция в процессоре не может быть выполнена быстрее, чем за один такт (период) генератора. Итак, минимальное время исполнения одной логической операции (переключение транзистора) - один такт. Тактовая частота измеряется в Герцах – число тактов в секунду.
-
 
+
Другой обобщенной мерой производительности ПК может служить число команд, выполняемые в единицу времени. Для вычислителей фон-Нейманновской архитектуры скорость выполнения команд уже может быть параметром, который может быть использован для оценки времени выполнения программы. Этот параметр - MIPS (Million Instruction Per Second)- миллион операций (команд, инструкций ЭВМ)/сек. Так как время выполнения различных команд может различаться, то данных параметр сопровождался разного вида уточнениями (логических команд, заданной смеси команд и т.д.), а также наиболее известной здесь мерой в 1 MIPS – это производительность вычислителя VAX 11/780. Итак, данный параметр также достаточно условен.
-
Другой обобщенной мерой производительности ПК может служить число команд, выполняемых в единицу времени. Для вычислителей фон-Нейманновской архитектуры скорость выполнения команд уже может быть параметром, который может быть использован для оценки времени выполнения программы. Этот параметр - MIPS (Million Instruction Per Second)- миллион операций (команд, инструкций ЭВМ)/сек. Так как время выполнения различных команд может различаться, то данных параметр сопровождался разного вида уточнениями (логических команд, заданной смеси команд и т.д.), а также наиболее известной здесь мерой в 1 MIPS – это производительность вычислителя VAX 11/780. Итак, данный параметр также достаточно условен.
+
-
 
+
Так как для большинства вычислительных алгоритмов существуют оценки числа арифметических операций, необходимых для выполнения расчетов, данная мера и может служить тем показателем, который и интересует пользователей в первую очередь. Это – MFLPOPS (Million of Floating point Operation Per Second – Мегафлопс)- миллион операций на данных с плавающей запятой/сек, единица быстродействия ЭВМ в операциях с плавающей запятой, есть также единицы - GFLPOPS и ТFLPOPS (терафлопс = 10**12 оп./сек.).
Так как для большинства вычислительных алгоритмов существуют оценки числа арифметических операций, необходимых для выполнения расчетов, данная мера и может служить тем показателем, который и интересует пользователей в первую очередь. Это – MFLPOPS (Million of Floating point Operation Per Second – Мегафлопс)- миллион операций на данных с плавающей запятой/сек, единица быстродействия ЭВМ в операциях с плавающей запятой, есть также единицы - GFLPOPS и ТFLPOPS (терафлопс = 10**12 оп./сек.).
Строка 1275: Строка 1256:
Ключевыми элементами OpenMP являются
Ключевыми элементами OpenMP являются
-
* конструкции для создания потоков (директива parallel),
+
* конструкции для создания потоков (директива parallel),
-
* конструкции распределения работы между потоками (директивы DO/for и section),
+
* конструкции распределения работы между потоками (директивы DO/for и section),
-
* конструкции для управления работой с данными (выражения shared и private),
+
* конструкции для управления работой с данными (выражения shared и private),
-
* конструкции для синхронизации потоков (директивы critical, atomic и barrier),
+
* конструкции для синхронизации потоков (директивы critical, atomic и barrier),
-
* процедуры библиотеки поддержки времени выполнения (например, omp_get_thread_num),
+
* процедуры библиотеки поддержки времени выполнения (например, omp_get_thread_num),
-
* переменные окружения (например, OMP_NUM_THREADS).
+
* переменные окружения (например, OMP_NUM_THREADS).
Строка 1376: Строка 1357:
= Порождение параллельных процессов. Идентификация абонентов. =
= Порождение параллельных процессов. Идентификация абонентов. =
-
== Идентификация абонентов ==
+
Идентификация абонентов
Идентификация абонентов при организации передачи сообщений может производится по имени процесса (массиву имен) или идентификатору задачи, по описанию которой образован процесс. Есть способы безадресных (широковещательных) посылок сообщений - "всем", и приема от произвольного отправителя сообщений с заказанной "маркой" - тегом. Идентификация абонентов может быть произведена:
Идентификация абонентов при организации передачи сообщений может производится по имени процесса (массиву имен) или идентификатору задачи, по описанию которой образован процесс. Есть способы безадресных (широковещательных) посылок сообщений - "всем", и приема от произвольного отправителя сообщений с заказанной "маркой" - тегом. Идентификация абонентов может быть произведена:
-
=== По имени процесса ===
+
а) По имени процесса
Основным способом идентификации абонентов при передаче сообщений является задание имени процесса (системного идентификатора) переменными типа TASKID и стандартными функциями этого типа MYTASKID, РАRENT и МАSTER. Использование этих стандартных функций является единственным первоначальным способом сослаться из порождаемых процессов на имена порождающих процессов, так как начальный диалог между процессами возможен только на уровне порожденный-порождаемый. Путем обмена сообщениями можно организовать передачу имен процессов для организации произвольной абонентской сети.
Основным способом идентификации абонентов при передаче сообщений является задание имени процесса (системного идентификатора) переменными типа TASKID и стандартными функциями этого типа MYTASKID, РАRENT и МАSTER. Использование этих стандартных функций является единственным первоначальным способом сослаться из порождаемых процессов на имена порождающих процессов, так как начальный диалог между процессами возможен только на уровне порожденный-порождаемый. Путем обмена сообщениями можно организовать передачу имен процессов для организации произвольной абонентской сети.
Переменные типа TASKID - параметры операторов передачи сообщений могут:
Переменные типа TASKID - параметры операторов передачи сообщений могут:
-
* ссылаться на функционирующий процесс,
+
- ссылаться на функционирующий процесс,
-
* ссылаться на завершенный процесс,
+
 
-
* иметь значение .NOTASKID.,
+
- ссылаться на завершенный процесс,
-
* быть не инициализированными.
+
 
 +
- иметь значение .NOTASKID.,
 +
 
 +
- быть не инициализированными.
Реакция программы на три последних случая не оговаривается в языке и определяется реализацией. Одно из решений - игнорирование оператора обмена сообщениями с такими параметрами (кроме синхронных операторов, для которых такой случай следует считать "авостом" в программе). Процесс-отправитель имеет возможность организовать дублирование передаваемых сообщений для передачи их одновременно нескольким процессам-получателем. Для этого допускается задание абонентов в параметрах оператора передачи сообщений в виде массива типа TASKID. Сообщение будет передано при этом всем процессам, на которые есть ссылки через элементы массива. Данная массовая операция предпочтительнее передачи сообщений, организованной по-элементной циклической конструкцией. Цикл предписывает порядок перебора элементов массива - абонентов передачи, а для синхронного обмена и завершение очередной передачи до посылки следующего сообщения. Массовая операция обмена может проводиться параллельно и независимо для всех заказанных абонентов. Массовые операции ассиметричны, нельзя заказать ожидание сообщения от нескольких процессов сразу. Теговая идентификация сообщений и конструкции выбора допускает не¬которую вольность в указаниях об именах отправителей.
Реакция программы на три последних случая не оговаривается в языке и определяется реализацией. Одно из решений - игнорирование оператора обмена сообщениями с такими параметрами (кроме синхронных операторов, для которых такой случай следует считать "авостом" в программе). Процесс-отправитель имеет возможность организовать дублирование передаваемых сообщений для передачи их одновременно нескольким процессам-получателем. Для этого допускается задание абонентов в параметрах оператора передачи сообщений в виде массива типа TASKID. Сообщение будет передано при этом всем процессам, на которые есть ссылки через элементы массива. Данная массовая операция предпочтительнее передачи сообщений, организованной по-элементной циклической конструкцией. Цикл предписывает порядок перебора элементов массива - абонентов передачи, а для синхронного обмена и завершение очередной передачи до посылки следующего сообщения. Массовая операция обмена может проводиться параллельно и независимо для всех заказанных абонентов. Массовые операции ассиметричны, нельзя заказать ожидание сообщения от нескольких процессов сразу. Теговая идентификация сообщений и конструкции выбора допускает не¬которую вольность в указаниях об именах отправителей.
-
=== По имени программной единицы-задачи ===
+
б) По имени программной единицы-задачи
-
Задание в операторе передачи сообщений в качестве адресата - получателя имени программной единицы-задачи означает рассылку сообщений всем процессам, образованным по описанию указанной задачи на момент выполнения оператора. Случай, когда к этому моменту не было образовано ни одного процесса по указанному образцу, можно рассматривать по аналогии с передачей сообщения процессу с "именем" - .NOTASKID. Возможность задать в качестве адресата имя главного процесса уточняется в описаниях входных версий языка.
+
Задание в операторе передачи сообщений в качестве адресата - получателя имени программной единицы-задачи означает рассылку сообщений всем процессам, образованным по описанию указанной задачи на момент выполнения оператора. Случай, когда к этому моменту не было образовано ни одного процесса по указанному образцу, можно рассматривать по аналогии с передачей сообщения процессу с "именем" - .NOTASKID. . Возможность задать в качестве адресата имя главного процесса уточняется в описаниях входных версий языка.
-
=== Безымянные абоненты ===
+
в) Безымянные абоненты
-
Специальный идентификатор ALL в параметре адресата-получателя сообщения предписывает передать данное сообщение всем процессам программы, инициализированным на данный момент.
+
Специальный идентификатор ALL в параметре адресата-получателя со¬общения предписывает передать данное сообщение всем процессам програм¬мы, инициализированным на данный момент.
Передача сообщений двумя последними способами предполагает возможность параллельной рассылки сообщений и исключение процесса, выполняющего оператор передачи сообщения, из списка абонентов - получателей.
Передача сообщений двумя последними способами предполагает возможность параллельной рассылки сообщений и исключение процесса, выполняющего оператор передачи сообщения, из списка абонентов - получателей.
-
=== Помеченные сообщения ===
+
г) Помеченные сообщения
При передаче сообщений асинхронным способом сообщения при отправлении помечаются целым числом - тегом. Эта разметка дает возможность абонентам идентифицировать сообщения от разных операторов передачи сообщений одного процесса. Получив сообщение с заданным тегом, процесс может узнать имя отправителя, через аппарат SENDERов. Это замечание верно и для передачи сообщений без ожидания.
При передаче сообщений асинхронным способом сообщения при отправлении помечаются целым числом - тегом. Эта разметка дает возможность абонентам идентифицировать сообщения от разных операторов передачи сообщений одного процесса. Получив сообщение с заданным тегом, процесс может узнать имя отправителя, через аппарат SENDERов. Это замечание верно и для передачи сообщений без ожидания.
Строка 1407: Строка 1391:
Операторы SEND и RECEIVE имеют вид:
Операторы SEND и RECEIVE имеют вид:
-
SEND (sm [,ss]...) [список]
+
1.0
-
RECEIVE (rm [,rs]...) [список]
+
SEND (sm [,ss]...) [список] RECEIVE (rm [,rs]...) [список]
-
, где sm или rm - спецификация сообщения - определяет адресата
+
1.5 где
 +
sm или rm - спецификация сообщения - определяет адресата
(процесс или процессы, которым посылается
(процесс или процессы, которым посылается
сообщение) или отправителя и способ синхронизации;
сообщение) или отправителя и способ синхронизации;
Строка 1418: Строка 1403:
Вид спецификации сообщения sm и rm зависит от способа синхронизации.
Вид спецификации сообщения sm и rm зависит от способа синхронизации.
-
а) Синхронный способ:
+
а) Синхронный способ: sm есть [TASKID =] адресат,
-
sm есть [TASKID =] адресат,
+
где адресат есть adr или ALL, а
где адресат есть adr или ALL, а
Строка 1425: Строка 1409:
Если adr - имя программной единицы-задачи, то сообщение посылается всем процессам программы, образованным по образцу указанной программной единицы (исключая посылающую).процедуры.
Если adr - имя программной единицы-задачи, то сообщение посылается всем процессам программы, образованным по образцу указанной программной единицы (исключая посылающую).процедуры.
-
ALL - означает, что сообщение посылается всем процессам программы, образованным на момент выполнения оператора передачи сообщения,исключая процесс-отправитель.
+
ALL - означает, что сообщение посылается всем процессам программы, образованным на момент выполнения оператора передачи сообщения,исключая процесс-отправитель. rm есть [TASKID =] t, где t - переменная или элемент массива типа TASKID; параметр специфицирует процесс - отправитель.
-
rm есть [TASKID =] t,
+
-
где t - переменная или элемент массива типа TASKID; параметр специфицирует процесс - отправитель.
+
Когда adr (rm) - значение типа TASKID, оно должно ссылаться на незавершенный процесс.
Когда adr (rm) - значение типа TASKID, оно должно ссылаться на незавершенный процесс.
б) Асинхронный способ
б) Асинхронный способ
-
sm есть [TAG=] ie, [TASKID =] адресат
+
sm есть [TAG=] ie, [TASKID =] адресат
-
или TASKID = адресат, [TAG =] ie
+
 
-
rm есть [TAG=] ie [,[TASKID =] t]
+
или TASKID = адресат, [TAG =] ie
-
или TASKID = t, [TAG =] ie
+
 
 +
rm есть [TAG=] ie [,[TASKID =] t]
 +
 
 +
или TASKID = t, [TAG =] ie
где адресат и t определяются как rm для синхронного способа,
где адресат и t определяются как rm для синхронного способа,
ie - выражение целого типа, значение которого определяет тег сообщения.
ie - выражение целого типа, значение которого определяет тег сообщения.
- 
в) Способ без ожидания
в) Способ без ожидания
-
sm есть [TASKID =] адресат, FLAG = l
+
 
-
rm есть [TASKID =] adr, FLAG = l
+
sm есть [TASKID =] адресат, FLAG = l
-
или [FLAG =] l
+
 
 +
rm есть [TASKID =] adr, FLAG = l
 +
 
 +
или [FLAG =] l
где
где
Строка 1480: Строка 1467:
2. Если значение переменной адресата есть .NOTASKID. или ссылка на завершенный процесс, оператор обмена для этого процесса не выполняется, а спецификация SENDER получает значение .NOTASKID. .
2. Если значение переменной адресата есть .NOTASKID. или ссылка на завершенный процесс, оператор обмена для этого процесса не выполняется, а спецификация SENDER получает значение .NOTASKID. .
- 
3.Не считается ошибкой наличие в почтовом ящике невостребованных сообщений при завершении процесса.
3.Не считается ошибкой наличие в почтовом ящике невостребованных сообщений при завершении процесса.
-
=== Использование операторов передачи сообщений ===
+
Использование операторов передачи сообщений
''Синхронный режим передачи сообщений''
''Синхронный режим передачи сообщений''
Строка 1497: Строка 1483:
Использование данного способа обмена сообщениями делает программу еще менее критичной к согласованию операторов обмена сообщениями, так как процесс-отправитель продолжает работу после передачи сообщения, не дожидаясь конца фактической передачи сообщения (и даже начала, так как система интерпретации "должна" сразу же, скопировав передаваемые данные в буфер, "отпустить" процесс) . Получатель сообщений этого типа может выдавать директиву приема сообщения, только удостоверившись в наличии нужного сообщения в почтовом ящике процесса при помощи функций: TESTMSG,TESTTAG,PROBE. Выполнение оператора RECEIVE без проверки наличия сообщения в почтовом ящике процесса, по аналогии с синхронным способом обмена, приводит к задержки выполнения процесса до приема со¬общения с заказанным тегом и ,возможно, с заданным именем отправителя. Но в отличие от синхронного способа, асинхронный способ позволяют про¬водить селекцию поступающих сообщений при помощи конструкций выбора. Пусть процесс может получать сообщения с тегом 1, но от процесса TI - скаляр целого типа, а от процесса TM(1) - массив из 100 целых чисел. Тогда,прием таких сообщений может быть запрограммированно так:
Использование данного способа обмена сообщениями делает программу еще менее критичной к согласованию операторов обмена сообщениями, так как процесс-отправитель продолжает работу после передачи сообщения, не дожидаясь конца фактической передачи сообщения (и даже начала, так как система интерпретации "должна" сразу же, скопировав передаваемые данные в буфер, "отпустить" процесс) . Получатель сообщений этого типа может выдавать директиву приема сообщения, только удостоверившись в наличии нужного сообщения в почтовом ящике процесса при помощи функций: TESTMSG,TESTTAG,PROBE. Выполнение оператора RECEIVE без проверки наличия сообщения в почтовом ящике процесса, по аналогии с синхронным способом обмена, приводит к задержки выполнения процесса до приема со¬общения с заказанным тегом и ,возможно, с заданным именем отправителя. Но в отличие от синхронного способа, асинхронный способ позволяют про¬водить селекцию поступающих сообщений при помощи конструкций выбора. Пусть процесс может получать сообщения с тегом 1, но от процесса TI - скаляр целого типа, а от процесса TM(1) - массив из 100 целых чисел. Тогда,прием таких сообщений может быть запрограммированно так:
-
IF (TESTTAG(1)) THEN
+
IF (TESTTAG(1)) THEN
-
SELECT MESSAGE
+
 
-
CASE(1,TI)
+
SELECT MESSAGE
-
RECEIVE (1) K
+
 
-
CASE(1,TM(1))
+
CASE(1,TI)
-
RECEIVE (1) KM
+
 
-
END SELECT
+
RECEIVE (1) K
-
END IF
+
 
-
или:
+
CASE(1,TM(1))
 +
 
 +
RECEIVE (1) KM
 +
 
 +
END SELECT
 +
 
 +
END IF или:
 +
 
 +
SELECT MESSAGE
 +
 
 +
CASE(1,TI)
 +
 
 +
RECEIVE (1) K
 +
 
 +
CASE(1,TM(1))
 +
 
 +
RECEIVE (1) KM
 +
 
 +
CASE DEFAULT
 +
 
 +
GO TO 2
 +
 
 +
END SELECT 2 CONTINUE
 +
 
 +
Ожидание этих сообщений, то есть, по аналогии с синхронной переда¬чей сообщений, прерывание работы процесса до получения сообщения (в данном случае любого из ожидаемого) записывается так:
 +
 
 +
SELECT MESSAGE
 +
 
 +
CASE(1,TI)
 +
 
 +
RECEIVE (1) K
 +
 
 +
CASE(1,TM(1))
 +
 
 +
RECEIVE (1) KM
 +
 
 +
END SELECT
 +
 
 +
Если сообщения различаются тегами, то конструкция их ожидания мо¬жет иметь вид:
 +
 
 +
SELECT MESSAGE
-
SELECT MESSAGE
+
CASE(1)
-
CASE(1,TI)
+
-
RECEIVE (1) K
+
-
CASE(1,TM(1))
+
-
RECEIVE (1) KM
+
-
CASE DEFAULT
+
-
GO TO 2
+
-
END SELECT
+
-
2 CONTINUE
+
-
Ожидание этих сообщений, то есть, по аналогии с синхронной передачей сообщений, прерывание работы процесса до получения сообщения (в данном случае любого из ожидаемого) записывается так:
+
RECEIVE (1) K
-
SELECT MESSAGE
+
CASE(2,TM(1))
-
CASE(1,TI)
+
-
RECEIVE (1) K
+
-
CASE(1,TM(1))
+
-
RECEIVE (1) KM
+
-
END SELECT
+
-
Если сообщения различаются тегами, то конструкция их ожидания может иметь вид:
+
RECEIVE (2) KM
-
SELECT MESSAGE
+
END SELECT
-
CASE(1)
+
-
RECEIVE (1) K
+
-
CASE(2,TM(1))
+
-
RECEIVE (2) KM
+
-
END SELECT
+
-
''Режим передачи сообщений без ожидания''
+
Режим передачи сообщений без ожидания
Передачи сообщений этого типа рекомендуется использовать для пере¬дачи данных "впрок", заблаговременно. Если после операторов SEND / RECEIVE без ожидания, поместить операторы: CALL MSDONE(L),
Передачи сообщений этого типа рекомендуется использовать для пере¬дачи данных "впрок", заблаговременно. Если после операторов SEND / RECEIVE без ожидания, поместить операторы: CALL MSDONE(L),
Строка 1635: Строка 1643:
С фиксированной запятой числа изображаются в виде последовательности цифр с постоянным для всех чисел положением запятой, отделяющей целую часть от дробной. Например, 32,54; 0,0036; –108,2. Эта форма проста, естественна, но имеет небольшой диапазон представления чисел и поэтому не всегда приемлема при вычислениях. Если в результате операции получится число, выходящее за допустимый диапазон, происходит переполнение разрядной сетки и дальнейшие вычисления теряют смысл. В современных компьютерах форма представления чисел с фиксированной запятой используется только для целых чисел.
С фиксированной запятой числа изображаются в виде последовательности цифр с постоянным для всех чисел положением запятой, отделяющей целую часть от дробной. Например, 32,54; 0,0036; –108,2. Эта форма проста, естественна, но имеет небольшой диапазон представления чисел и поэтому не всегда приемлема при вычислениях. Если в результате операции получится число, выходящее за допустимый диапазон, происходит переполнение разрядной сетки и дальнейшие вычисления теряют смысл. В современных компьютерах форма представления чисел с фиксированной запятой используется только для целых чисел.
-
С плавающей запятой числа изображаются в виде X = ±M×P±r, где M - мантисса числа (правильная дробь в пределах 0,1 ≤ M < 1), r - порядок числа (целое), P - основание системы счисления. Например, приведенные выше числа с фиксированной запятой можно преобразовать в числа с плавающей запятой так: 0,3254×10^2, 0,36×10^–2, –0,1082×10^3. Нормализованная форма представления имеет огромный диапазон чисел и является основной в современных ЭВМ.
+
С плавающей запятой числа изображаются в виде X = ±M×P±r, где M - мантисса числа (правильная дробь в пределах 0,1 ≤ M < 1), r - порядок числа (целое), P - основание системы счисления. Например, приведенные выше числа с фиксированной запятой можно преобразовать в числа с плавающей запятой так: 0,3254×102, 0,36×10–2, –0,1082×103. Нормализованная форма представления имеет огромный диапазон чисел и является основной в современных ЭВМ.
Каждому двоичному числу можно поставить в соответствие несколько видов кодов. Существуют следующие коды двоичных чисел:
Каждому двоичному числу можно поставить в соответствие несколько видов кодов. Существуют следующие коды двоичных чисел:
Строка 1774: Строка 1782:
-
== Попарное суммирование ==
 
-
Ниже представлен алгоритм, в цикле обрабатывающий массив — на каждой итерации суммируются числа парами, при этом размер массива уменьшается вдвое.
 
-
<pre>
 
-
/* Pairwise Summation */
 
- 
-
float fp_add(float * flt_arr)
 
-
{
 
-
long i, j, limit;
 
-
float sum[ARR_SIZE / 2 + 1];
 
- 
-
if (ARR_SIZE == 2)
 
-
return flt_arr[0] + flt_arr[1];
 
-
else if (ARR_SIZE == 1)
 
-
return flt_arr[0];
 
- 
-
for (i = j = 0; i < ARR_SIZE / 2; i++, j += 2)
 
-
sum[i] = flt_arr[j] + flt_arr[j + 1];
 
-
if (ARR_SIZE & 1)
 
-
sum[ARR_SIZE / 2] = flt_arr[ARR_SIZE - 1];
 
-
limit = (ARR_SIZE + 1) / 2;
 
- 
-
while (limit > 2) {
 
-
for (i = j = 0; i < limit / 2; i++, j += 2)
 
-
sum[i] = sum[j] + sum[j + 1];
 
- 
-
if (limit & 1)
 
-
sum[limit / 2] = sum[limit - 1];
 
-
limit = (limit + 1) / 2;
 
-
}
 
- 
-
return sum[0] + sum[1];
 
-
}
 
-
</pre>
 
-
Данный алгоритм работает быстрее, чем упорядоченное суммирование, и при этом дает более аккуратный результат.
 
== Оценка полной ошибки для суммирования положительных чисел. ==
== Оценка полной ошибки для суммирования положительных чисел. ==
Пример расчета полной ошибки для суммирования положительных чисел
Пример расчета полной ошибки для суммирования положительных чисел
Строка 1835: Строка 1809:
Последствия таких преобразований обсуждались выше. Наиболее характерные преобразования следующие.
Последствия таких преобразований обсуждались выше. Наиболее характерные преобразования следующие.
-
'''1. Балансировка дерева вычислений'''
+
1. Балансировка дерева вычислений
Балансировка дерева вычислений (tree-height reduction or balancing) выражений позволяют использовать конвейерное АУ без пропуска рабочих тактов. Так, вычисление суммы вещественных чисел: A+B+C+D+E+F+G+H, будет запрограммировано как последовательность операций: (((A+B)+(C+D))+((E+F)+(G+H))); это нарушает заданную по умолчанию последовательность вычислений с накоплением одной частной суммы и может повлиять на результат.
Балансировка дерева вычислений (tree-height reduction or balancing) выражений позволяют использовать конвейерное АУ без пропуска рабочих тактов. Так, вычисление суммы вещественных чисел: A+B+C+D+E+F+G+H, будет запрограммировано как последовательность операций: (((A+B)+(C+D))+((E+F)+(G+H))); это нарушает заданную по умолчанию последовательность вычислений с накоплением одной частной суммы и может повлиять на результат.
-
'''2. Исключение общих подвыражений'''
+
2. Исключение общих подвыражений
Алгоритмы исключения общих подвыражений (Common subexpession elimination) также могут изменить порядок вычислений.
Алгоритмы исключения общих подвыражений (Common subexpession elimination) также могут изменить порядок вычислений.
Если компилятор распознает в выражениях повторяющееся вычисление, то это вычисление производятся один раз, его результат сохраняется на регистре, и в дальнейшем используется этот регистр. Тем самым исключается избыточность вычислений.
Если компилятор распознает в выражениях повторяющееся вычисление, то это вычисление производятся один раз, его результат сохраняется на регистре, и в дальнейшем используется этот регистр. Тем самым исключается избыточность вычислений.
Строка 1845: Строка 1819:
Y = E + REG
Y = E + REG
-
'''3. Разворачивание циклов'''
+
3. Разворачивание циклов
Разворачивание циклов (loop unrolling) - расписывание цикла последовательностью операторов присваивания: либо полностью, либо размножение тела цикла с некоторым коэффициентом (фактором) размножения.
Разворачивание циклов (loop unrolling) - расписывание цикла последовательностью операторов присваивания: либо полностью, либо размножение тела цикла с некоторым коэффициентом (фактором) размножения.
Производится частичное или полное разворачивание цикла в последовательный участок кода. При частичном разворачивании используется так называемый фактор разворачивания (который можно задавать в директиве компилятору).
Производится частичное или полное разворачивание цикла в последовательный участок кода. При частичном разворачивании используется так называемый фактор разворачивания (который можно задавать в директиве компилятору).
Строка 1857: Строка 1831:
DO I=1,10 DO I=1,10,2
DO I=1,10 DO I=1,10,2
S = S + A(I) S = S + A(I)
S = S + A(I) S = S + A(I)
-
ENDDO S1 = S1 + A(I+1)
+
ENDDO S1 = S1 + A(A+1)
ENDDO
ENDDO
S = S + S1
S = S + S1
Здесь, суммирование проводится отдельно для четных и нечетных элементов с последующем сложением частных сумм.
Здесь, суммирование проводится отдельно для четных и нечетных элементов с последующем сложением частных сумм.
- 
-
{{Курс ПОД (3 поток)}}
 

Пожалуйста, обратите внимание, что все ваши добавления могут быть отредактированы или удалены другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. eSyr's_wiki:Авторское право).
НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!


Отменить | Справка по редактированию (в новом окне)

Шаблоны, использованные на этой странице:

Получено с http://esyr.org/wiki/%D0%9F%D0%9E%D0%94_%283_%D0%BF%D0%BE%D1%82%D0%BE%D0%BA%29%2C_%D0%9E%D1%82%D0%B2%D0%B5%D1%82%D1%8B
Личные инструменты
Разделы