Основы информатики

Размещено на http://www.allbest.ru/

КУРС ЛЕКЦИЙ

на тему: «Основы информатики»

Содержание

Тема №1. Предмет, объекты и основные части информатики, системы счисления

1. Термин «информация», формы представления информации

1.1 Системы счисления, виды

1.2 Системы счисления и основы логики

Тема №2. Архитектура современной вычислительной техники. Представление информации в компьютере. Булева алгебра

2.1 Единицы измерения информации

2.2 Представление числовой и текстовой информации

Тема №3. Управление памятью, мультипроцессорные вычислительные системы

3.1 Классификация систем параллельной обработки данных

3.2 Многопроцессорные системы с общей памятью

3.3 Многопроцессорные системы с локальной памятью и многомашинные системы

Тема №4. Программное обеспечение компьютера

4.1 Системное программное обеспечение

4.2 ОС MS DOS и программная оболочка Norton Commander

4.3 ОС Windows: концепция, основные понятия

Тема №5. Введение в программирование. Основы алгоритмизации задач. Алгоритмы и алгоритмизация

5.1 Определение и свойства алгоритмов

5.2 Виды алгоритмов

Тема №6. Прикладное программное обеспечение ОС WINDOWS: Текстовый редактор WORD. Электронные таблицы EXCEL

6.1 Прикладные программы MS Office

6.2 Текстовый редактор MS Word: структура окна, основные элементы

6.3 Табличный процессор MS Excel: структура окна, основные элементы

Тема №7. Система управления базами данных ACCESS

7.1 Понятие о БД, виды БД

7.2 Реляционная БД ACCESS

7.3 Основные свойства полей таблиц баз данных СУБД Microsoft Access

Тема №8. Компьютерные сети, сетевые и телекоммуникационные технологии. Компьютерные сети. Локальные сети. Глобальная сеть Интернет

8.1 Понятие и классификация компьютерных сетей

8.2 Топология вычислительных сетей

8.3 Интернет и основные понятия, связанные с глобальной сетью

8.4 Принципы защиты информации

Тема №9. Основы защиты информации. Безопасность и защита информации. Защита информации в локальных сетях

9.1 Компьютерные вирусы

9.2 Классификация вирусов

9.3 Основные меры по защите от вирусов

Тема №10. Системы искусственного интеллекта

10.1 Искусственный интеллект

10.2 Экспертные системы

10.3 Классификация экспертных систем

Тема №11. Современные программные средства. Инструментарий технологии программирования. Современные языки высокого уровня

11.1 Программа и программирование

11.2 Язык программирования Pascal: структура, алфавит, типы данных

11.3 Операторы языка Pascal

информация система счисление программа

Тема №/1 Предмет, объекты и основные части информатики, системы счисления

1. Термин «информация», формы представления информации

1.1 Системы счисления, виды

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

Термин «информация» происходит от латинского слова «informatio» - разъяснение, осведомление, изложение. Говоря «информация», мы имеем в виду и сообщения по радио и телевидению, и содержание газет, книг, баз данных, библиотек, и знания, взятые из общения с людьми и полученные в научных журналах. Информацию хранят в книгах, библиотеках, в базах, данных, на бумаге и машинных носителях. Информацию передают устно и письменно, с помощью электрических сигналов и радиоволн; получают с помощью органов чувств, электрических датчиков фото и видеокамер.

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

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

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

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

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

- Аналоговую (непрерывную) - температура тела; мелодия, извлекаемая на скрипке, когда смычок не отрывается от струн и не останавливается; движение автомобиля.

- Дискретную (прерывистую) - времена года, точка и тире в азбуке Морзе

1.2 Системы счисления и основы логики

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

Системы счисления разделяют на две группы: позиционные и непозиционные.

В непозиционной системе счисления смысл каждой цифры не зависит от занимаемой ею позиции. Примером такой системы является римская система. В числе ХХХ, записанной в этой системе, цифра Х в любой позиции означает 10 (десять).

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

В позиционной системе счисления значение цифры зависит от ее места (позиции). Основанием позиционной системы счисления называется число используемых цифр в системе.

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

Двоичная система

В двоичной системе любое число записывается с помощью двух цифр 0 и 1 и называется двоичным числом. Основание системы равно 2. Каждый разряд (цифру) двоичного числа называют битом. При записи чисел значение каждой цифры зависит от ее положения.

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

Перевод числа из десятичной системы счисления в двоичную:

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

Например, 227₁₀=11100011₂

227 : 2 остаток 1

113 : 2 остаток 1

56 : 2 остаток 0

28 : 2 остаток 0

14 : 2 остаток 0

7 : 2 остаток 1

3 : 2 остаток 1

и последнее частное = 1

б) десятичная дробь последовательно умножается на основание 2, причем сразу после каждой операции умножения полученная целая часть записывается в результат и в дальнейшем умножении не участвует. Количество операций зависит от требуемой точности, например, 0,64₁₀=0,10100011₂

0,64*2

1,28*2

0,56*2

1,12*2

0,24*2

0,48*2

0,96*2

1,92*2

1,84*2

Перевод числа из двоичной системы в десятичную

Любое двоичное число можно записать с использованием степеней двойки. Например, число 1011₂ представляется в виде:

а) 1011₂=1*2³+0*2²+1*2¹+1*2⁰=11₁₀

б) 0,10100011₂=1*2^-1+0*2^-2+1*2^-3+0*2^-4+0*2^-5+0*2^-6+1*2^-7+1*2^-8=0,5+0,125+0,0078+0,0039=0,6367₁₀

Представление отрицательных чисел

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

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

Форма значения со знаком - старший (левый) разряд метится как знаковый и содержит информацию о знаке числа: 1 - число отрицательное, 0 - число положительное.

5₁₀=0000 0101₂

-5₁₀=1000 0101₂

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

1) инвертировать все разряды числа, кроме знакового разряда

2) прибавить единицу к полученному коду

3) восстановить единицу в знаковом разряде

Например, -5₁₀=1000 0101₂>111 1010+1>111 1011>1111 1011

Правила выполнения арифметических операций в двоичной системе.

Правило сложения:

0+0=0

1+0=1

0+1=1

1+1=10

Например, 1 1 1 1 0 0 1 1

+ 1 1 1 0 1 1

1 0 01 0 1 1 1 0

Вычитание сводится к сложению с отрицательным числом. Алгоритм операции вычитания:

1) преобразовать отрицательное число из формы со знаком в дополнительный код

2) выполнить операцию сложения

3) при равенстве 1 знакового разряда суммы (отрицательный результат) необходимо перевести результат в знаковую форму. Например, 13-15=13+(-15)

1)-15₁₀=10001111>1110000+1>1110001>11110001

2) 00001101

+11110001

11111110

3) 1111 1110>000 0001+1>1000 0010=-2₁₀

Восьмеричная система

В восьмеричной системе, числа выражаются с помощью цифр: 0,1, 2, 3, 4, 5, 6, 7. Например:

357₈=3 * 8²+5*8¹+ 7*8⁰=239₁₀

Шестнадцатеричная система

В шестнадцатеричной позиционной системе счисления для записи чисел используются цифры десятичной системы счисления 0, 1, 2, 3, 4, 5, 6 , 7, 8, 9 и для обозначения шести недостающих цифр используются первые прописные буквы латинского алфавита: A, B, C, D, E, F имеющие значения десятичных чисел 10, 11, 12, 13, 14 и 15 соответственно.

Позиционные системы счисления

	Двоичная	Восьмеричная	Шестнадцатеричная
0	0000	0	0
1	0001	1	1
2	0010	2	2
3	0011	3	3
4	0100	4	4
5	0101	5	5
6	0110	6	6
7	0111	7	7
8	1000	10	8
9	1001	11	9
10	1010	12	A
11	1011	13	B
12	1100	14	C
13	1101	15	D
14	1110	16	E
15	1111	17	F
16	10000	20	10

Каждая тройка двоичных разрядов соответствует одной восьмеричной цифре, а каждая четверка - шестнадцатеричной. Если исходно количество бит не кратно 3 или 4, добавляются нули слева.

Например, 11010011₂=1101 0011₂=D3₁₆

11010011₂=011 010 011₂=323₈

Обратное преобразование аналогично: В9₁₆=1011 1001₂

270₈=010 111 000₂

Перевод из десятичной системы счисления в m-ричную производится аналогично переводу в двоичную систему, т.е. путем целочисленного деления на основание системы m.

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

Тема №2 Архитектура современной вычислительной техники. Представление информации в компьютере. Булева алгебра

2.1 Единицы измерения информации

1. Единица информации называется битом. Термин "бит" предложен как аббревиатура от английского словосочетания "Binary digit", которое переводится как "двоичная цифра".

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

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

В компьютерной технике бит соответствует физическому состоянию носителя информации: намагничено - не намагничено, есть отверстие - нет отверстия. При этом одно состояние принято обозначать цифрой 0, а другое - цифрой 1. Выбор одного из двух возможных вариантов позволяет также различать логические истину и ложь. Последовательностью битов можно закодировать текст, изображение, звук или какую-либо другую информацию. Такой метод представления информации называется двоичным кодированием (binary encoding).

В информатике часто используется величина, называемая байтом (byte) и равная 8 битам. И если бит позволяет выбрать один вариант из двух возможных, то байт, соответственно, 1 из 256 (2⁸).

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

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

1 Кбайт (один килобайт) = 2¹⁰ байт = 1024 байта;

1 Мбайт (один мегабайт) = 2¹⁰ Кбайт = 1024 Кбайта = 2²⁰ байт;

1 Гбайт (один гигабайт) = 2¹⁰ Мбайт = 1024 Мбайта = 2³⁰ байт.

В последнее время в связи с увеличением объёмов обрабатываемой информации входят в употребление такие производные единицы, как:

1 Тбайт (один терабайт) = 2¹⁰ Гбайт = 1024 Гбайт = 2⁴⁰ байт,

1 Пбайт(один петабайт) = 2¹⁰ Тбайт = 1024 Тбайт = 2⁵⁰ байт.

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

2.2 Представление числовой информации

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

Представление текстовой информации.

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

С точки зрения ЭВМ текст состоит из отдельных символов. К числу символов принадлежат не только буквы (заглавные или строчные, латинские или русские), но и цифры, знаки препинания, спецсимволы типа "=", "(", "&" и т.п. и даже (обратите особое внимание!) пробелы между словами. Да, не удивляйтесь: пустое место в тексте тоже должно иметь свое обозначение.

Каждый символ хранится в виде двоичного кода, который является номером символа. Можно сказать, что компьютер имеет собственный алфавит, где весь набор символов строго упорядочен. Количество символов в алфавите также тесно связано с двоичным представлением и у всех ЭВМ равняется 256. Иными словами, каждый символ всегда кодируется 8 битами, т.е. занимает ровно один байт.

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

Наиболее стабильное положение в алфавитах всех ЭВМ занимают латинские буквы, цифры и некоторые специальные знаки. Это связано с существованием международного стандарта ASCII (American Standard Code for Information Interchange - Американский стандартный код для обмена информацией). Русские же буквы не стандартизированы и могут иметь различную кодировку.

3. Алгебра логики, созданная в середине 18 века англичанином Дж. Булем (булева алгебра) оперирует с логическими переменными. Основополагающим законом алгебры логики является закон исключения третьего, согласно которому логические переменные, в отличие от переменных обычной алгебры, могут принимать только два значения. Переменные обычно обозначаются, как и двоичные цифры, символами 0 и 1. Операции над переменными записываются с помощью логических операций.

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

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

Таблица 1

X	Y	{X*YXY}	{X+YXY}	{X` X}
0	0	0	0	1
0	1	0	1	1
1	0	0	1	0
1	1	1	1	0
		(a)	(b)	(c)

Существует несколько булевых операций, из которых только три: И (AND), ИЛИ (OR) и НЕ (NOT) полагаются базовыми, остальные можно получать на их основе. Операция И называется логическим умножением или конъюнкцией, обозначается знаком {* } умножения и определяется табл. 1 (а). Операция ИЛИ называется логическим сложением или дизъюнкцией, обозначается знаком {+ } и определяется табл. 1 (b). Наконец, операция НЕ называется логическим отрицанием или инверсией (дополнением), обозначается знаком {` } и определяется табл. 1 (с); табл. 1 задает аксиомы (постулаты) булевой алгебры. Таким образом, булева алгебра определяется множеством элементов B={0,1}, множеством операций {И, ИЛИ, НЕ} и аксиомами, переделяемыми табл. 3.

Этапы построения логической схемы:

составляется таблица истинности;

по таблице истинности строится логическая функция с помощью СДНФ(совершенной дизъюнктивной нормальной формы);

по возможности полученная формула минимизируется;

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

Основные соотношения (теоремы) булевой алгебры можно сформулировать в виде следующих законов (табл. 2):

Таблица 2. Основные законы булевой алгебры

1.	{01}`={10}; x+0=x*1=x; x+1=1; x*0=0	-//-//-//-//-//-
2.	x+x=x; x*x=x	Идемпотентности
3.	(x`)`=x	Двойного отрицания
4.	x+y=y+x; x*y=y*x	Коммутативности
5.	x+x*y=x*(x+y)=x; x+x`* y=x+y; x*(x`+y)=x*y	Поглощения
6.	(x+y)`-x`*y`; (x*y)`=x`+y`	Моргана
7.	(x+y)+z=x+(y+z)=x+y+z; (x*y)* z=x*(y*z)=x*y*z	Ассоциативности
8.	x+y*z=(x+y)*(x+z); x* (y+z)=x*y+x*z	Дистрибутивности

Логические основы ЭВМ.

Элемент И (AND gate).

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

Условное обозначение и таблица истинности элемента "И" с двумя выходами.

	А2	0	1	0	1
Выход	В	0	0	0	1

Элемент ИЛИ (OR gate).

Электронный логический вентиль, на выходе которого логический 0 (значение "ложь") появляется только тогда, когда на все его выходы (два и более) поданы сигналы логического 0; во всех остальных случаях на выходе появляется логическая 1 (значение "истина"). Этот вентиль реализует логическую операцию ИЛИ и имеет аналогичную с ней таблицу истинности.

	А2	0	1	0	1
Выход	В	0	1	1	1

Элемент НЕ-И (штрих Шеффера).

Электронная логическая схема, в которой выходной сигнал имеет уровень логической 0 (ложь) только тогда, когда на всех ее входах действуют сигналы логической 1. Во всех других случаях на его выходе появляется логическая 1.

	А2	0	1	0	1
Выход	В	1	1	1	0

Вентиль НЕ-И эквивалентен И с инвертированным выходом.

Элемент ИЛИ-НЕ(стрелка Пирса).

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

	А2	0	1	0	1
Выход	В	1	0	0	0

Практически любые схемы могут быть построены на одних только элементах ИЛИ-НЕ.

Элемент НЕ (NOT gate).

Электронный логический вентиль, инвертирующий входной сигнал, т.е. преобразующий логический 0 в логическую 1 и наоборот.

Выход В	И	Л

Элемент ИСКЛЮЧАЮЩЕЕ ИЛИ.

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

	А2	0	1	0	1
Выход	В	0	1	1	0

Элемент ИСКЛЮЧАЮЩЕЕ НЕ-ИЛИ.

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

	А2	0	1	0	1
Выход	В	1	0	0	1

Карты Карно.

Количество клеток в карте равно количеству строчек в таблице истинности.

Соседними считаются клетки карты, отличающиеся значениями только одной переменной. Минимализацию логической формулы при небольшом количестве переменных (до 5) удобно проводить с помощью карты Карно. Здесь группы из 2, 4, 8 и т.д. соседних ячеек, содержащих единицы, если они расположены так, что их можно обвести контуром в виде прямоугольника или квадрата, могут быть описаны одним логическим произведением. В это произведение входят только неизмененные для всех ячеек данной группы переменные.

Тема №3. Управление памятью, мультипроцессорные вычислительные системы

3.1 Классификация систем параллельной обработки данных

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

Параллельные ЭВМ часто подразделяются по классификации Флинна на машины типа SIMD (Single Instruction Multiple Data - с одним потоком команд при множественном потоке данных) и MIMD (Multiple Instruction Multiple Data - с множественным потоком команд при множественном потоке данных). Как и любая другая, приведенная выше классификация несовершенна: существуют машины прямо в нее не попадающие, имеются также важные признаки, которые в этой классификации не учтены. В частности, к машинам типа SIMD часто относят векторные процессоры, хотя их высокая производительность зависит от другой формы параллелизма - конвейерной организации машины. Многопроцессорные векторные системы, типа Cray Y- MP, состоят из нескольких векторных процессоров и поэтому могут быть названы MSIMD (Multiple SIMD). Классификация Флинна не делает различия по другим важным для вычислительных моделей характеристикам, например, по уровню "зернистости" параллельных вычислений и методам синхронизации. Можно выделить четыре основных типа архитектуры систем параллельной обработки:

1) Конвейерная и векторная обработка.

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

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

2) Машины типа SIMD.

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

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

Модели вычислений на векторных и матричных ЭВМ настолько схожи, что эти ЭВМ часто обсуждаются как эквивалентные.

3) Машины типа MIMD.

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

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

4) Многопроцессорные машины с SIMD-процессорами.

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

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

Многопроцессорные системы за годы развития вычислительной техники претерпели ряд этапов своего развития. Исторически первой стала осваиваться технология SIMD. Однако в настоящее время наметился устойчивый интерес к архитектурам MIMD. Этот интерес главным образом определяется двумя факторами:

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

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

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

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

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

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

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

К первой группе относятся машины с общей (разделяемой) основной памятью, объединяющие до нескольких десятков (обычно менее 32) процессоров. Сравнительно небольшое количество процессоров в таких машинах позволяет иметь одну централизованную общую память и объединить процессоры и память с помощью одной шины. При наличии у процессоров кэш-памяти достаточного объема высокопроизводительная шина и общая память могут удовлетворить обращения к памяти, поступающие от нескольких процессоров. Поскольку имеется единственная память с одним и тем же временем доступа, эти машины иногда называются UMA (Uniform Memory Access). Такой способ организации со сравнительно небольшой разделяемой памятью в настоящее время является наиболее популярным. Структура подобной системы представлена на рис.1.

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

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

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

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

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

Рис.2. Типовая архитектура машины с распределенной памятью.

Как уже было отмечено, любая крупномасштабная многопроцессорная система должна использовать множество устройств памяти, которые физически распределяются вместе с процессорами. Имеется две альтернативных организации адресации этих устройств памяти и связанных с этим два альтернативных метода для передачи данных между процессорами. Физически отдельные устройства памяти могут адресоваться как логически единое адресное пространство, что означает, что любой процессор может выполнять обращения к любым ячейкам памяти, предполагая, что он имеет соответствующие права доступа. Такие машины называются машинами с распределенной разделяемой (общей) памятью (DSM - distributed shared memory), масштабируемые архитектуры с разделяемой памятью, а иногда NUMA's - Non-Uniform Memory Access, поскольку время доступа зависит от расположения ячейки в памяти.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2 Многопроцессорные системы с общей памятью

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

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

Мультипроцессорная когерентность кэш-памяти

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

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

1. Протоколы на основе справочника (directory based). Информация о состоянии блока физической памяти содержится только в одном месте, называемом справочником (физически справочник может быть распределен по узлам системы). Этот подход будет рассмотрен в разд.3.

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

Рис.3. Иллюстрация проблемы когерентности кэш-памяти

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

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

С этим простым определением согласованного состояния памяти мы можем гарантировать когерентность путем обеспечения двух свойств:

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

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

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

Необходимость строго последовательного выполнения операций записи является более тонким, но также очень важным свойством. Представим себе, что строго последовательное выполнение операций записи не соблюдается. Тогда процессор P1 может записать данные в ячейку, а затем в эту ячейку выполнит запись процессор P2. Строго последовательное выполнение операций записи гарантирует два важных следствия для этой последовательности операций записи. Во-первых, оно гарантирует, что каждый процессор в машине в некоторый момент времени будет наблюдать запись, выполняемую процессором P2. Если последовательность операций записи не соблюдается, то может возникнуть ситуация, когда какой-нибудь процессор будет наблюдать сначала операцию записи процессора P2, а затем операцию записи процессора P1, и будет хранить это записанное P1 значение неограниченно долго. Более тонкая проблема возникает с поддержанием разумной модели порядка выполнения программ и когерентности памяти для пользователя: представьте, что третий процессор постоянно читает ту же самую ячейку памяти, в которую записывают процессоры P1 и P2; он должен наблюдать сначала значение, записанное P1, а затем значение, записанное P2. Возможно он никогда не сможет увидеть значения, записанного P1, поскольку запись от P2 возникла раньше чтения. Если он даже видит значение, записанное P1, он должен видеть значение, записанное P2, при последующем чтении. Подобным образом любой другой процессор, который может наблюдать за значениями, записываемыми как P1, так и P2, должен наблюдать идентичное поведение. Простейший способ добиться таких свойств заключается в строгом соблюдении порядка операций записи, чтобы все записи в одну и ту же ячейку могли наблюдаться в том же самом порядке. Это свойство называется последовательным выполнением (сериализацией) операций записи (write serialization). Вопрос о том, когда процессор должен увидеть значение, записанное другим процессором достаточно сложен и имеет заметное воздействие на производительность, особенно в больших машинах.

3.3 Многопроцессорные системы с локальной памятью и многомашинные системы