Типы вершин блок-схем алгоритмов
| Обозначение | Пояснение |
 | Функциональнаявершина − имеет один вход и один выход |
 | Предикатная вершина – имеет один вход и два выхода. Функция Р передаёт управление по одной из ветвей в зависимости от значения функции Р, которое может принимать значения true (истина) и false (ложь). |
 | Объединяющая вершина (вершина «слияния») – обеспечивает передачу управления от одного из двух входов к выходу. |
Графы находят также применение в химии (для описания структур, путей сложных реакций), в теории электрических цепей, в экономике, в логистике, и т.д.
3.7 Вопросы и тестовые задания для самоконтроля
1. К понятиям формальной логики НЕ относится:
1) абстрагирование;
2) истинность;
3) высказывание;
4) эквивалентность.
2. Что изучает математическая логика?
3. Что такое алгебра логики?
4. Дайте определение высказыванию и приведите примеры высказываний.
5. Какие операции отношения применяются в языках программирования?
6. Какие логические операции вы знаете?
7. Приведите таблицы истинности для каждой из логических операций.
8. Логическое высказывание «Оля – отличница, но плохая спортсменка» является истинным, когда:
1) Оля отличница и плохая спортсменка;
2) Оля отличница или плохая спортсменка;
3) Оля отличница или плохая спортсменка;
4) Оля отличница и хорошая или плохая спортсменка.
9. Укажите логическую операцию (?), заданную таблицей истинности:
Х Y X ? Y
1 1 0
1 0 1
0 1 1
0 0 0
1) XOR;
2) OR;
3) EQV;
4) IMP;
10. Составьте таблицы истинности для утверждений:
1 (не А) и (не В);
2 А и (не В);
3 (не А) или (не В);
4 А или (не В).
11. Перечислите базовые логические элементы функциональных узлов ЭВМ и их условные обозначения.
12. Укажите правильное соотношение множеств А и В:
1) BÌА
2) AÈB
3) АÇВ
4) В – А
13. Определите заштрихованную область:
1) BÌА
2) AÈB
3) АÇВ
4) В – А
14. Определите заштрихованную область:
1) BÌА
2) AÈB
3) АÇВ
4) В – А
15. Определите заштрихованную область:
1) BÌА
2) AÈB
3) АÇВ
4) В – А
вернуться к содержанию
ТЕХНИЧЕСКИЕ СРЕДСТВА РЕАЛИЗАЦИИ ИНФОРМАЦИОННЫХ ПРОЦЕССОВ
В данном разделе приводятся основные сведения об истории, архитектуре и принципах функционирования технических средств реализации информационных процессов.
История развития ЭВМ
Устройства, облегчающие счёт или запоминание его результатов, известны давно. Это абак (четыре тысячи лет до нашей эры) и русские счёты (XVI в.). Но они не обладали главным свойством компьютера – производить вычисления автоматически. Автоматические вычисления, заключающиеся в генерации и регистрации сигналов (перемещений) через определённые промежутки времени, производят механические часы (XIV в.). Первая счётная машина была построена французским учёным Блезом Паскалем в 1642 г. Она была механической с ручным приводом и могла выполнять операции сложения и вычитания. Немецкий математик Готфрид Лейбниц в 1672 г. построил механическую машину, которая могла делать также операции умножения и деления. В 1804 г. в ткацком станке Жаккарда была реализована идея гибкого программного управления с помощью перфорированной бумажной ленты.
Впервые машину, работающую по программе, разработал в 1834 г. английский учёный Чарльз Бэббидж. Она содержала запоминающее устройство, вычислительное устройство, устройство ввода с перфокарт и печатающее устройство. Команды считывались с перфокарты и выполняли считывание данных из памяти в вычислительное устройство и запись в память результатов вычислений. Все устройства машины Бэббиджа, включая память, были механическими и содержали тысячи шестерёнок, при изготовлении которых требовалась точность, недоступная в XIX в. Первым программистом можно назвать Аду Лавлейс, предложившей использовать перфокарты для программирования.
Герман Холлерит, сотрудник американского Национального бюро по переписи населения, создал в 1887 г. первый электромеханический табулятор. Принцип работы этой счётной машины основан на замыкании электрической цепи через отверстия перфокарты, приведении в действие исполнительного механизма и увеличении показаний соответствующего счётчика на единицу. В 1896 г. Холлерит основал фирму Tabulating Machihe Company, которая была поглощена компанией Computer Tabulating Recording Company, переименованной позже в International Business Machihe (IBM).
В XX в. начала развиваться электроника, и её возможности немедленно взяли на вооружение разработчики вычислительных машин. С построения вычислительных машин, базовая система элементов которых была построена на электронных компонентах, начинается отсчёт поколений ЭВМ. Отметим, что деление периода развития цифровой техники на этапы связано, в основном, с переводом базовой системы элементов на новые технологии производства электронных компонентов.
Первое поколение – электронные лампы (1945–1955 гг.) Их использование определяло и достоинства, и недостатки цифровых устройств. Электронные лампы обеспечивали высокую скорость переключения логических элементов, что увеличивало скорость вычисления по сравнению с попытками создать вычислительную машину, базовый элемент которой был построен на основе электромеханического реле. Электронные лампы были достаточно долговечны и обеспечивали надёжную работу компьютера. К сожалению, недостатков у ламповых компьютеров тоже было достаточно. Электронные лампы работали с напряжениями в десятки вольт и расходовали много энергии, кроме того, размер электронных ламп, по современным понятиям микроэлектроники, был огромным – несколько десятков кубических сантиметров. Для построения вычислительной машины нужны были тысячи логических элементов, поэтому размер ламповых вычислительных машин по занимаемой площади составлял десятки квадратных метров, а потребляемая мощность колебалась в пределах от единиц до десятков и даже сотен киловатт. Скорость обработки информации в ламповых машинах колебалась от нескольких сотен до нескольких тысяч операций в секунду.
Второе поколение – транзисторы (1955–1965 гг.). Они отличались от электронных ламп малыми размерами, низким напряжением питания и малой потребляемой мощностью. Новая элементная база для компьютеров на основе транзисторов произвела революцию в производстве компьютеров. Значительное уменьшение габаритов, снижение потребляемой мощности и стоимости позволило создавать архитектуры компьютера с большими функциональными возможностями, резко повысить быстродействие компьютеров до сотен тысяч и даже миллионов операций в секунду. Увеличение производительности обеспечивалось как за счёт более высокой скорости работы транзисторов по сравнению с электронными лампами, так и путём введения в состав вычислительной машины нескольких обрабатывающих устройств, работающих параллельно. Площадь, требуемая для размещения компьютера, снизилась до нескольких квадратных метров, предпринимались попытки изготавливать и настольные варианты. Снижение стоимости увеличило число потенциальных пользователей компьютеров. Появились крупные фирмы по производству компьютеров широкого назначения: International Business Machines (IBM), Control Data Corporation (CDC), Digital Equipment Corporation (DEC) и др. Следует отметить компьютер PDP-8 фирмы DEC – первого мини-компьютера с общей шиной, оказавшего большое влияние на развитие архитектур персональных компьютеров.
Третье поколение – интегральные схемы (1965–1980 гг.). Требование уменьшения габаритов электронных устройств привело к тому, что сначала полупроводниковые приборы стали производиться в бескорпусном исполнении, а затем в 1958 г. была предпринята попытка разместить в одном полупроводниковом кристалле все компоненты одного функционального узла. Так появились интегральные схемы (ИС), которые позволили резко уменьшить размеры полупроводниковых схем и снизить потребляемую мощность. На основе ИС строились мини-ЭВМ, которые выполнялись в виде одной стойки и периферийных устройств. Мощность, потребляемая компьютером на ИС, уменьшилась до сотен ватт. Увеличение быстродействия узлов, построенных на ИС, позволило довести быстродействие компьютеров до десятков миллионов операций в секунду. Электронная промышленность приступила к массовому производству электронных компонентов на ИС, что позволило снизить их стоимость и резко уменьшить стоимость аппаратной составляющей компьютеров. Уменьшение стоимости привело к разработке и практической реализации мощных вычислительных систем, использующих параллельную обработку: многопроцессорные и конвейерные вычислители.
Четвёртое поколение – сверхбольшие интегральные схемы (с 1980 гг.) Используя последние научно-технические достижения физики, химии, кристаллографии, материаловедения и даже космонавтики (в невесомости можно получить полупроводниковые кристаллы очень высокой чистоты), удалось достичь размещения на одном кристалле размером несколько квадратных миллиметров сначала сотен, затем тысяч и, наконец, миллионов транзисторов и других электронных компонентов. Теперь полупроводниковая схема содержала уже не набор нескольких логических элементов, из которых строились затем функциональные узлы компьютера, а целиком функциональные узлы и, в первую очередь процессор, который, учитывая его размеры, получил название микропроцессор, устройства управления внешними устройствами – контроллеры внешних устройств. Такие микросхемы большой и сверхбольшой степени интеграции получили название больших (БИС) и сверхбольших интегральных схем (СБИС) соответственно. Итогом такого бурного развития микроэлектроники стало появление одноплатных и однокристальных ЭВМ, где на одной плате, размером несколько десятков квадратных сантиметров, размещались СБИС, содержащие все функциональные блоки компьютера. Одноплатные компьютеры встраивались в различные промышленные, медицинские и бытовые приборы для оперативной обработки информации и управления.
Стоимость одноплатных компьютеров так упала, что появилась возможность их приобретения отдельными людьми. Такой возможностью воспользовались английские инженеры Стив Джобс и Стив Возняк. Используя выпускаемые промышленностью функциональные узлы: плата микро-ЭВМ с процессором и памятью, клавиатура, дисплей, они собрали дешёвую настольную вычислительную машину – микрокомпьютер. Его привлекательность для непрофессиональных пользователей заключалась в том, что это было готовое к употреблению устройство, содержащее всё необходимое оборудование и программное обеспечение для работы. Этот микрокомпьютер получил название Apple и стал первым в мире персональным компьютером.
Персональными компьютерами, которые получили большое распространение на компьютерном рынке, заинтересовалась крупная компания, занимавшаяся выпуском мощных вычислительных систем, – IBM, и решила наладить выпуск своей модели персонального компьютера. Совместно с фирмой Intel, разработавшей микропроцессорный комплект, и фирмой Microsoft, которая оснастила компьютер операционной системой MS DOS, IBM создала персональный компьютер IBM PC. Значительный потенциал фирмы IBM позволил в короткие сроки произвести огромное количество таких компьютеров. Их привлекательная для покупателей цена и некоторые новшества, например, больший, по сравнению с выпускавшимися в то время персональными компьютерами других фирм, объём оперативной памяти, позволили компьютеру IBM PC стать самой популярной «персоналкой» в мире.
Дальнейшая классификация вычислительных систем по их принадлежности к различным поколениям весьма условна. В настоящее время элементная база микропроцессорных систем активно развивается, но в её основе по-прежнему лежат СБИС. Количество элементов в современных многоядерных процессорах приближается к миллиарду. Некоторые специалисты выделяют пятое, шестое и последующие поколения как усовершенствование микроэлектронных технологий (многопроцессорные компьютеры, оптоэлектроника, криоэлектроника, нанотехнологии). Другие рассматривают последующие поколения как изменение структур обработки команд и данных внутри микропроцессора (нейрокомпьютеры с системами логического вывода, естественным речевым и видеоинтерфейсом).
Классификация ЭВМ
Наиболее часто при выборе компьютера для той или иной сферы применения используется такая характеристика, как производительность, под которой понимается время, затрачиваемое компьютером для решения той или иной задачи. Можно считать, что производительность является некоторой интегрированной характеристикой, определяющей общую вычислительную мощность компьютера и, соответственно, области его применения. На производительность компьютера влияют следующие параметры: тактовая частота (количество элементарных операций в секунду, например 3,4 ГГц – гигагерц); разрядность (количество обрабатываемой за один такт информации, например 32 или 64 бит); объём памяти, время доступа к ней и др. Вполне естественно, что компьютер с высокой скоростью обработки должен снабжаться большим объёмом оперативной памяти, так как иначе его производительность будет ограничена необходимостью подкачки информации из более медленной внешней памяти.
Часто оценка производительности указывается в количестве ФЛОПС (FLOPS – FLoating Operations Per Second – операций над числами с плавающей запятой). Например, 100 МFLOPS – сто мегафлопс. По производительности компьютеры можно условно разбить на три класса: суперкомпьютеры; мэйнфреймы; микрокомпьютеры.
Суперкомпьютеры – компьютеры с самой высокой производительностью (свыше 100 млн операций в секунду). Применяются для решения таких задач, как моделирование физических процессов, гидрометеорология, космические исследования и других задач, которые требуют огромных объёмов вычислений. Выполняются обычно по многопроцессорной архитектуре, имеют большой набор внешних устройств и, как правило, выпускаются небольшими партиями или даже создаются в единственном экземпляре – для решения конкретной задачи или конкретного заказчика. Обычно важность решаемой задачи такова, что основным параметром суперкомпьютера является его высокая производительность, а такие параметры, как стоимость, размеры или вес, не являются определяющими. Производительность современных суперкомпьютеров измеряется в ТФЛОПС (терафлопс – 1012 ФЛОПС) и достигает десятков петафлопс (1015 ФЛОПС). Так, первое место в рейтинге 500 суперкомпьютерных систем мира (www.top500.org) по состоянию на ноябрь 2012 г. занимает «Titan - Cray XK7» производства компании Cray Inc с максимальной производительностью 17,59 петафлопс. При этом «Titan» содержит из 560640 вычислительных ядер, а потребляемая мощность составляет 8209 кВт.
Мэйнфреймы – компьютеры с средней производительностью порядка 100 млн операций в секунду. Они используются для решения таких задач, как хранение, поиск и обработка больших массивов данных, построение трёхмерной анимационной графики, создание рекламных роликов, выполняют роль узлов глобальной сети, используемой торговыми или компьютерными фирмами с большим потоком запросов. Выполняются по многопроцессорной архитектуре с общей шиной и небольшим числом мощных процессоров. Конструктивно выполняются в виде одной стойки или в настольном варианте.
Микрокомпьютеры – компактные компьютеры универсального назначения, в том числе и для бытовых целей, имеющие сравнительно небольшую производительность. Микрокомпьютеры, или персональные компьютеры, можно классифицировать по конструктивным особенностям: стационарные (desktop-настольные) и переносные.
Переносные компьютеры, в свою очередь, можно разделить на портативные (laptop), блокноты (notebook) и карманные (Palmtop). Портативные компьютеры по размеру близки к обычному портфелю, они в настоящее время уступают место более компактным ноутбукам, которые по размеру близки к книге крупного формата и имеют массу около 2 кг. Такие компьютеры имеют встроенные аккумуляторы, позволяющие работать без сетевого напряжения. Обязательным является наличие средств компьютерной связи. В настоящее время имеются полноцветные жидкокристаллические мониторы, не уступающие по качеству мониторам стационарных компьютеров.
Карманные компьютеры ещё называют наладонниками. Это класс портативных электронных вычислительных устройств, изначально предложенных к использованию в качестве электронных органайзеров. Они не имеют внешней памяти на магнитных дисках, она заменена на энергонезависимую электронную память. Эта память может перезаписываться при помощи линии связи с настольным компьютером. В английском языке словосочетание «карманный ПК» (Pocket PC) не является обозначением всего класса устройств, а является торговой маркой фирмы Майкрософт, т.е., относится лишь к одной из разновидностей КПК. Английское словосочетание Palm PC (наладонный компьютер) также ассоциируется с совершенно конкретной торговой маркой. Для обозначения всего класса устройств в английском языке используется словосочетание Personal Digital Assistant, PDA, что на русский можно перевести как «личный цифровой секретарь». Карманный компьютер можно использовать как словарь-переводчик или интеллектуальную записную книгу. Всё большее распространение получают коммуникаторы или смартфоны, совмещающие в себе функции компьютера и мобильного телефона.
Важным классификационным признаком является совместимость. От совместимости зависит взаимозаменяемость компонентов (аппаратная совместимость), переносимость программ (совместимость на уровне операционных систем и программная совместимость) и возможность совместной работы разнотипных компьютеров с данными (совместимость на уровне данных).
Архитектура ЭВМ
К понятию архитектуры ЭВМ относят следующие основы построения ЭВМ: совокупность основных устройств, узлов и блоков; структура основных управляющих и информационных связей между ними; система команд; способы обращения к памяти и внешним устройствам; форматы данных; организация интерфейса.
Для изучения принципа работы каждого узла и компьютера в целом вводятся различные уровни его представления (по степени обобщения). Набор блоков, связей между ними, типов данных и операций каждого уровня называется архитектурой уровня.
Цифровой логический уровень – самый низкий, детальный уровень логических схем базовой системы элементов – инверторы, сумматоры, триггеры и др.
Микроархитектурный уровень – уровень организации обработки информации внутри функционального узла. Сюда относятся регистры различного назначения, устройство обработки поступающих команд, устройство преобразования данных, устройство управления.
Командный уровень – набор функциональных узлов и связей между ними, система команд и данных, передаваемых между устройствами. Именно архитектура командного уровня и называется обычно компьютерной архитектурой или компьютерной организацией. Основателем архитектуры большинства современных компьютеров является американский математик
Принцип использования двоичной системы обеспечивает простоту технической реализации.
Принцип хранимой программы совмещает в себе идеи программного управления (программа – последовательность команд), однородности памяти (в одной и той же памяти хранятся и программа, и данные) и адресности (ячейки памяти пронумерованы, по этим номерам-адресам происходит обращение к содержимому).
Принцип логического устройства ЭВМ определяет структуру, состоящую из следующих основных блоков: арифметико-логическое устройство (АЛУ), производящее все вычисления; устройство управления (УУ), координирующее взаимодействие различных блоков ЭВМ; запоминающее устройство для хранения информации; устройство ввода-вывода информации. Один из вариантов фон-неймановской архитектуры представлен на рисунке 4.1.
Рис. 4.1. Архитектура фон-неймановской ЭВМ
Программа, т.е. совокупность машинных команд, записывается в память ОЗУ в соседние ячейки по возрастанию их адресов, а данные, которые требуют обработки, – в ячейки с произвольными адресами. Каждая команда содержит код операции, которую необходимо выполнить, и адреса ячеек, в которых находятся данные, обрабатываемые этой командой. Устройство управления содержит специальный регистр, который называется «Счётчик команд». После загрузки программы и данных в память в счётчик команд записывается адрес первой команды программы. Устройство управления считывает из памяти содержимое ячейки памяти, адрес которой находится в счётчике команд, и помещает его в специальное устройство – «Регистр команд». Регистр команд хранит команду во время её исполнения. Устройство управления расшифровывает тип операции команды, считывает из памяти данные, адреса которых указаны в команде, и приступает к её выполнению. Для каждой команды устройство управления имеет свой алгоритм обработки, который заключается в выработке управляющих сигналов для всех остальных устройств машины.
Первые поколения ЭВМ не имели возможности подключения дополнительных функциональных блоков и устройств, не предусмотренных разработчиком. Это так называемая закрытая архитектура, т.е. с фиксированный набор устройств. В начале 1970-х гг. фирмой DEC (Digital Equipment Corporation) был создан компьютер с общей шиной, реализующей принцип открытой архитектуры и дающей возможность подключения любых устройств в соответствии со стандартом шины. Шина (совокупность линий передачи сигналов) подразделяется на шину данных, шину адреса и шину управления. Для согласования сигналов внешних устройств с шиной подключение осуществляется через специальные устройства – контроллеры или адаптеры (рис. 4.2). Контроллер, по сути, является специализированным процессором, управляющим работой внешнего устройства по встроенной программе. Организация взаимодействия между внешним устройством и процессором осуществляется через аппаратный или программный порт ввода-вывода – канал передачи данных, представляемый как один или несколько адресов памяти, из которых можно прочитать или в которые можно записать данные.
Рис. 4.2. Архитектура ЭВМ с общей шиной
Достоинством архитектуры с общей шиной является возможность дополнять ЭВМ новыми элементами в зависимости от конкретных целей и задач и заменять устаревшие блоки. Недостатком является задержка «быстрых» устройств при работе «медленных». Дальнейшее повышение производительности компьютера было найдено во введении дополнительного контроллера и локальной шины, к которой подключались только «быстрые» устройства.
Для получения высокого быстродействия на существующей элементной базе используются архитектуры, в которых процесс обработки распараллеливается и выполняется одновременно на нескольких обрабатывающих устройствах. Существует три основных подхода к построению архитектур таких компьютеров: многопроцессорные, магистральные и матричные архитектуры.
Архитектура самых простых многопроцессорных систем выполняется по схеме с общей шиной. Несколько процессоров и общая память подключаются к общей шине. Каждый процессор при необходимости проверяет, свободна ли шина, и, если она свободна, занимает её. Если шина занята, процессор ждёт, пока она освободится. При увеличении числа процессоров производительность системы ограничивается пропускной способностью шины. Для снижения нагрузки на общую шину каждый процессор дополнительно снабжается собственной локальной памятью. Один из процессоров выделяется для управления всей системой. Он распределяет задания на исполнение программ между процессорами и управляет работой общей шины. Для выполнения операций управления внешними устройствами в этой и других архитектурах обычно устанавливается специализированный периферийный процессор.
Магистральный принцип является наиболее распространённым при построении высокопроизводительных вычислительных систем. Процессор такой системы состоит из быстрой регистровой памяти для хранения обрабатываемых данных и нескольких функциональных обрабатывающих устройств, каждое выполняет только один вид вычислительных операций (сложение, умножение, деление, сдвиг и т.д.). Данные, считанные из памяти, размещаются в регистрах. Устройство планирования последовательности выполнения команд направляет данные, хранящиеся в регистрах, на соответствующие функциональные устройства. Полученные результаты снова записываются в регистры и служат исходными данными для дальнейших вычислений. Конечные результаты вычислений записываются в общее запоминающее устройство. Таким образом, получается конвейер преобразования данных: регистры – обрабатывающие устройства – регистры и т.д.
Матричная архитектура вычислительной системы является наиболее сложной. В ней процессоры объединяются в матрицу процессорных элементов. Каждый процессорный элемент снабжён локальной памятью, хранящей обрабатываемые процессором данные. Процессорные элементы могут производить обмен или со своими соседями, или с общим запоминающим устройством. В качестве процессорных элементов могут использоваться универсальные процессоры, имеющие собственные устройства управления, или вычислители, содержащие только АЛУ и выполняющие команды внешнего устройства управления. В первом случае, программы и данные нескольких задач или независимых частей одной задачи загружаются в локальную память процессоров и выполняются параллельно. Во втором случае все процессорные элементы одновременно выполняют одну и ту же команду, поступающую от устройства обработки команд на все процессорные элементы, но над разными данными, хранящимися в локальной памяти каждого процессорного элемента. Обмен данными с периферийными устройствами выполняется через периферийный процессор, подключённый к общему запоминающему устройству.