1. Информация. Меры Хартли, Шеннона. 3

2. Знания и ЭВМ. 4

3. Критерий, положенный в основу эволюционной классификации ЭВМ. 7

4. Основоположники отечественной вычислительной техники. 8

5. Принципы фон-Нейманновской архитектуры ЭВМ. 8

6. Конвейерная обработка данных. 9

7. Зацепление конвейеров. 9

8. Векторно-конвейерные вычислители. 10

9. CISC и RISC архитектуры ЭВМ. 10

10. Внеочередное и спекулятивное выполнения команд. 10

11. Механизмы предсказания переходов. 10

12. Управление виртуальной памятью. 11

13. Ассоциативная память. 11

14. Назначение и структура кэш-памяти. 12

15. Полностью ассоциативная кэш-память. 13

16. Кэш-память с прямым отображением. 13

17. Частично ассоциативная кэш-память. 14

18. Дисциплина обновления кэш-памяти. 14

19. Стратегии записи в кэш-память. 15

20. Расслоение памяти. 15

21. Принципы VLIW архитектуры. 16

22. Суперскалярные и мультитредовые архитектуры микропроцессоров. 16

23. Стандарт IA-64. 17

24. Оптимизация программ под архитектуру микропроцессора. 18

25. Гетерогенные распределенные вычислительные системы. 18

26. Метакомпъютинг. 18

27. Кластерные архитектуры. 19

28. Симметричные мультипроцессорные системы. 20

29. Матричные мультипроцессорные системы. 20

30. Классификации вычислителей по Флинну. 21

31. Масштабируемость мультипроцессорных вычислителей. 21

32. Управление памятью в мультипроцессорных системах. 21

33. Когерентность данных. 21

34. Типы внутренних связей. 22

35. Статические и динамические коммуникаторы. 23

36. Параметры статических коммутационных сетей. 23

37. Топологии линейки, решетки, пирамиды. 23

38. Топология гиперкуба. 23

39. Согласование сеточных топологий со структурой гиперкуба. 24

40. Перекрестный коммутатор. 24

41. Многокаскадные коммутационные сети. 24

42. Пиковая производительность. 25

43. Методы оценки производительности. 25

44. Закон Амдала. 26

45. Принципы потоковой обработки информации. 26

46. Схемы потоковых вычислителей. 26

47. Нейронные сети. 27

48. Области применения нейронных сетей. 28

49. Модели программирования для систем с разделяемой, распределенной памятью. 28

50. Разделение последовательных программ на параллельные нити. 29

51. Ограничения на распараллеливание циклов. 29

52. Синхронизация параллельных процессов. Барьеры. 29

53. Критические секции. Двоичные и общие семафоры. 31

54. Упорядоченные секции. Распараллелить цикл, используя упорядоченные секции и семафоры: 32

55. Статический и динамический способы образования параллельных процессов . 33

56. Требования к системам программирования методом передачи сообщений. 34

57. Система программирования MPI. 34

58. Средства описания и создания процессов в языке Фортран-GNS. 36

59. Средства передачи и приема сообщений в языке Фортран-GNS. 39

60. Протоколы передачи и приема сообщений в языке Фортран-GNS. 40

61. Идентификация абонентов при передачи сообщений в языке Фортран-GNS. 43

62. Автоматическое распараллеливание последовательных программ. 44

63. Семантика циклов, выполняемых параллельно на ОКМД системах. 44

64. Алгоритмы преобразования программ методом координат. 44

65. Схема преобразования программ методом гиперплоскостей. 47

66. Метод параллелепипедов. 48

67. Оценить возможность параллельного выполнения цикла: DO i = 2,N A(i) = (B(i) + (i))/A(i+CONST) ENDDO 48

68. Стандарты OpenMP. 49

69. Язык Фортран-DVM. 51

70. Язык Sisal. 52

71. Система программирования Норма. 54

72. Распараллеливание алгоритмов сложения методом редукции 55

73. Метод распараллеливания алгоритма общей рекурсии 1-го порядка. 57

74. Представление машинных чисел. 58

75. Арифметика машинных чисел. 58

76. Погрешности при вычислениях чисел на параллельных системах. Оценить полную ошибку суммирования положительных чисел. 58

77. Точность плавающей арифметики. Машинный эпсилон. 59

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

§9. Средства автоматического распараллеливания программ 60

1. Информация. Меры Хартли, Шеннона.

Различные формулировки понятия “информация”:

• В законодательном плане: сведения о лицах, предметах, фактах, событиях, явлениях и процессах независимо от формы их представления (ФЕДЕРАЛЬНЫЙ ЗАКОН Об информации, информатизации и защите информации);

• В концептуальном плане: универсальная субстанция, пронизывающая все сферы человеческой деятельности, служащая проводником знаний и мнений, инструментом общения, взаимопонимания и сотрудничества, утверждения стереотипов мышления и поведения (ЮНЕСКО); бесконечный законопроцесс триединства энергии, движения и массы в пространстве и во времени с различными плотностями кодовых структур бесконечно-беспредельной Вселенной. Информация внутри нас, информация вне нас. Есть законы существования этой информации внутри и вне нас (Международная Академия Информатизации)

• В математике, системном анализе — любая сущность, которая вызывает изменения в некоторой информационно-логической (инфологической — состоящей из сообщений, данных, знаний. абстракций и т. д.) модели, представляющей систему

• В термодинамике:

1. отрицание энтропии, отражение меры хаоса в системе (Бриллюэн);

2. передача разнообразия (Эшби);

3. мера сложности структур (Моль);

4. величина обратно пропорциональная беспорядку в системе;

5. отраженное разнообразие, то есть нарушение однообразия;

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

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

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

• Содержание, полученное от внешнего мира в процессе приспособления к нему (Винер)

• Абстрактное содержание какого-либо высказывания, описания, сообщения или известия

• Сообщения, осведомляющие о положении дел, о состоянии чего-нибудь, обмен сведениями.

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

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

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

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

Меры могут быть статические и динамические, в зависимости от того, какую информацию они позволяют оценивать: статическую (не актуализированную; на самом деле оцениваются сообщения без учета ресурсов и формы актуализации) или динамическую (актуализированную т.е. оцениваются также и затраты ресурсов для актуализации информации).

Мера Р. Хартли. Пусть имеется N состояний системы S или N опытов с различными, равновозможными, последовательными состояниями системы. Если каждое состояние системы закодировать, например, двоичными кодами определенной длины d, то эту длину необходимо выбрать так, чтобы число всех различных комбинаций было бы не меньше, чем N. Наименьшее число, при котором это возможно, называется мерой разнообразия множества состояний системы и задается формулой Р. Хартли: H=klog_аN, где k - коэффициент пропорциональности (масштабирования, в зависимости от выбранной единицы измерения меры), а - основание системы меры.

Если измерение ведется в экспоненциальной системе, то k=1, H=lnN (нат); если измерение было произведено в двоичной системе, то k=1/ln2, H=log₂N (бит); если измерение было произведено в десятичной системе, то k=1/ln10, H=lgN (дит).

Пример. Чтобы узнать положение точки в системе из двух клеток т.е. получить некоторую информацию, необходимо задать 1 вопрос ("Левая или правая клетка?"). Узнав положение точки, мы увеличиваем суммарную информацию о системе на 1 бит (I=log₂ 2). Для системы из четырех клеток необходимо задать 2 аналогичных вопроса, а информация равна 2 битам (I=log₂4). Если же система имеет n различных состояний, то максимальное количество информации будет определяться по формуле: I=log₂n.

Справедливо утверждение Хартли: если в некотором множестве X={x₁, x₂, ..., x_n} необходимо выделить произвольный элемент x_i X, то для того, чтобы выделить (найти) его, необходимо получить не менее log_an (единиц) информации.

Если N - число возможных равновероятных исходов, то величина klnN представляет собой меру нашего незнания о системе.

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

Мера К. Шеннона. Формула Шеннона дает оценку информации независимо, отвлеченно от ее смысла:

где n - число состояний системы; р_i - вероятность (или относительная частота) перехода системы в i-е состояние, причем сумма всех p_i равна 1.

Если все состояния равновероятны (т.е. р_i=1/n), то I=log₂n.

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

Пример. Время t реакции испытуемого на выбор предмета из имеющихся N предметов линейно зависит от log₂N: t=200+180log₂N (мс). По аналогичному закону изменяется и время передачи информации в живом организме. Один из опытов по определению психофизиологических реакций человека состоял в том, что перед испытуемым большое количество раз зажигалась одна из n лампочек, на которую он должен был указать в ходе эксперимента. Оказалось, что среднее время, необходимое для правильного ответа испытуемого, пропорционально не числу n лампочек, а именно величине I, определяемой по формуле Шеннона, где p_i - вероятность зажечь лампочку номер i

Легко видеть, что в общем случае

Если выбор i-го варианта предопределен заранее (выбора, собственно говоря, нет, p_i=1), то I=0.

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

См. также вопрос 2.

1. Знания и ЭВМ.

Аналоговые и непрерывные – АВМ

Цифровые и дискретные – ЭЦВМ, ЭВМ

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

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

• сообщения, полученные системой от внешнего мира в процессе адаптивного управления, приспособления (теория управления, кибернетика);

• отрицание энтропии, отражение меры хаоса в системе (термодинамика);

• связи и отношения, устраняющие неопределенность в системе (теория информации);

• вероятность выбора в системе (теория вероятностей);

• отражение и передача разнообразия в системе (физиология, биокибернетика);

• отражение материи, атрибут сознания, "интеллектуальности" системы (философия).

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

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

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

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