- •Лекция 1 Основные понятия Об информационно-библиотечной культуре
- •Информация, сведения, данные, знания
- •Лекция 2 Неформальные и формальные каналы коммуникации
- •Библиотеки, библиография и библиографическое описание
- •Библиотечная и информационная деятельность
- •Тенденции развития основных видов документов
- •Закономерности роста и старения
- •Оценка значимости (влиятельности) ученых и журналов
- •Закон рассеяния статей конкретной тематики по журналам
- •Лекция 3 Предыстория и сущность
- •Процедуры и понятия
- •Координатное индексирование
- •Цитирование, библиографическое сочетание, социтирование
- •Рубрикаторы информационных изданий
- •Лекция 4 Электронные издания
- •Информационные ресурсы, структуры и инфраструктура
- •Информационные продукты и услуги
- •Лекция 5 Основные понятия и проблемы становления информационного общества. Информатизация как процесс перехода к информационному обществу
- •Возникновение, этапы развития и технологические аспекты информатизации
- •Положительные и отрицательные последствия информатизации
- •Программы информатизации
- •Программы информатизации России
- •Электронное правительство
- •Лекция 6 Представления информации Сообщение как материальная форма представления информации
- •Формы сообщений (сигналы, изображения, знаки, языковые сообщения)
- •Основные понятия теории формальных языков
- •Модели источников сообщений. Конечный вероятностный источник сообщений
- •Кодирование сообщений источника и текстов. Равномерное кодирование. Дерево кода
- •Неравномерное кодирование. Средняя длина кодирования
- •Префиксные коды
- •Необходимые и достаточные условия существования префиксного кода с заданными длинами кодовых слов. Неравенство Крафта
- •Методы построения кодов. Код Фано
- •Избыточность кодирования. Нижняя граница средней длины кодирования
- •Оптимальное кодирование, свойства оптимальных кодов, построение оптимальных кодов методом Хафмена
- •Лекция 7 Модель процесса передачи. Двоичный симметричный канал
- •Способы повышения надежности передачи сообщений
- •Принципы обнаружения и исправления ошибок с использованием кодов
- •Расстояние Хеминга и корректирующие возможности кодов
- •Оценки верхних границ корректирующих способностей кодов
- •Особенности векторных пространств над конечным полем gf(2). Линейный групповой код
- •Построение линейного кода по заданной порождающей матрице
- •Декодирование линейного кода по синдрому
- •Описание процесса обработки данных. Понятие алгоритма и его свойства. Способы формальной записи алгоритмов
- •Модель процесса обработки данных. Конечные автоматы
- •Сеть Петри как модель параллельно выполняемых процессов обработки
- •Формальное определение сети Петри
- •Основные задачи анализа процессов обработки, решаемые с использованием сетей Петри
- •Матричный метод анализа сетей Петри
- •Иерархия информационных систем управления Трансакционные системы
- •Системы бизнес-интеллекта
- •Аналитические приложения
- •Сущность erp-систем
- •Управление запасами и производством
- •Управление спецификациями изделий и технологиями производства
- •Планирование операций
- •Управление продажами
- •Управление запасами
- •Управление закупками
- •Управление производственными процессами
- •Учет и управление финансами Сущность финансового и управленческого учета
- •Главная книга
- •Расчеты с дебиторами
- •Расчеты с кредиторами
- •Основные средства
- •Денежные средства
- •Материально-производственные запасы
- •Расчеты с персоналом
- •Налоговый учет
- •Бухгалтерская отчетность
- •Аналитические возможности
- •Управление персоналом
- •Ограниченность erp-систем
- •Сущность систем бизнес-интеллекта
- •Хранилища данных Функциональность
- •Olap-системы Функциональность
- •Средства формирования запросов и визуализации данных Функциональность
- •Основные виды аналитических приложений
- •Системы управления эффективностью бизнеса (bpm-системы) Сущность концепции bpm
- •Функциональность bpm-систем
- •Управление по ключевым показателям Balanced Scorecard и другие методики управления по ключевым показателям
- •Функциональность bsc-систем
- •Корпоративное планирование и бюджетирование Основы корпоративного планирования и бюджетирования
- •Многомерное хранение информации
- •План счетов
- •Календарь планирования
- •Мультивалютность
- •Бизнес-правила
- •Описание финансовой структуры предприятия
- •Описание пользователей
- •Сценарии и версии
- •Управление процессом планирования
- •Формирование и анализ консолидированной финансовой отчетности Сущность консолидированной финансовой отчетности
- •Информационные системы консолидации финансовой отчетности
- •Аналитические направления
- •Сбор и структурирование исходной информации
- •Мультивалютность
- •Бизнес-правила
- •Журналы
- •Организация процесса консолидации
- •Процедуры консолидации
- •Bi-приложения
- •Системы финансового моделирования
- •Системы имитационного моделирования
- •Определения и термины
- •Области применения имитационных моделей
- •Последовательность разработки имитационных моделей
- •Компьютерная реализация имитационной модели
- •Система Arena
- •Экспертные системы
- •Архитектура экспертной системы
- •Классы экспертных систем
- •Технология создания экспертных систем
- •Рекомендации по выбору экспертной системы
- •Системы поддержки принятия решений
- •Определение систем поддержки принятия решений
- •Характеристика различных систем поддержки принятия решений
- •Выделение признаков классификации сппр
- •Особенности Экспертной системы поддержки принятия решений
- •Архитектура эсппр
- •Реализация выбора метода принятия решения в эсппр
- •Характеристика эсппр по выделенным признакам
- •Специализированные аналитические приложения
- •Принципы построения компьютера История и тенденции развития вычислительной техники
- •Основные характеристики и классификация компьютеров
- •Принципы построения компьютера
- •Структурные схемы и взаимодействие устройств компьютера
- •Компьютерные системы
- •Системы счисления
- •Перевод целых чисел
- •Перевод дробных чисел
- •Арифметические основы эвм Представление числовой информации в компьютере
- •Машинные коды
- •Арифметические операции над числами с фиксированной точкой
- •Логические основы эвм Основные сведения из алгебры логики
- •Законы алгебры логики
- •Техническая интерпретация логических функций
- •Кодирование информации в компьютере
- •Кодирование нечисловой информации
- •Кодирование текстовой информации
- •Кодирование графических данных
- •Кодирование звуковой информации
- •Основная память
- •Сверхоперативная память
- •Ассоциативная память
- •Центральный процессор эвм
- •Система команд микропроцессора
- •Взаимодействие элементов при работе микропроцессора
- •Системы визуального отображения информации (видеосистемы)
- •Клавиатура
- •Принтеры
- •Внешние запоминающие устройства (взу)
- •Накопитель на жестком магнитном диске
- •Оптические запоминающие устройства
- •Организация функционирования эвм с магистральной архитектурой
- •Организация работы эвм при выполнении задания пользователя
- •Особенности управления основной памятью эвм
- •Система прерываний эвм
- •Параллельные вычисления
- •Характеристика и особенности лкс
- •Протоколы и технологии локальных сетей
- •Сетевые устройства лкс
- •Структурированная кабельная система и логическая структуризация лкс
- •Виды глобальных сетей
- •Глобальные сети России РосНиирос
- •Магистральная сеть науки и образования rbNet (Russian Backbone Network)
- •Сеть runNet
- •Узел маршрутизации Российского фонда фундаментальных исследований (рффи)
- •Msk-IX (Московский центр взаимодействия компьютерных сетей Internet eXchange)
- •Сервисы Internet
- •Isp (Internet Service Provider)
- •Ipp (Internet Presence Provider)
- •Pcp (Private Content Publisher)
- •Характеристики хостинг-провайдеров
- •Программное обеспечение Интернета
Параллельные вычисления
Вычислительный процесс - это последовательность целенаправленных действий по обработке информации, приводящих к достижению поставленной цели.
Вычислительный процесс характеризуется тремя параметрами:
составом событий, из которых он состоит;
продолжительностью каждого события (или операций по обработке события);
последовательностью возникновения событий.
Графически вычислительный процесс может изображаться трассой, временной диаграммой, ярусно-параллельным графом, и др.
Трасса представляется в виде упорядоченного множества событий , имевших место в моменты времени, причем
Трасса характеризует динамику процесса, т.е. развитие его во времени. Обычно она изображается в виде последовательности событий, нанесенных в масштабе на ось времени.
Развитие процесса в пространстве и во времени характеризуется временной диаграммой. Временная диаграмма обычно изображается на нескольких осях времени, причем каждая ось содержит трассу, которая характеризует загрузку одного из устройств, выделенных процессу.
Ярусно-параллельный граф характеризует параллельность (одновременность, параллелизм) выполнения действий, составляющих процесс.
Простейший вид параллелизма реализован в мультипрограммных системах - этот вид параллелизма называется "совмещение во времени различных этапов разных задач".
Мультипрограммная обработка возможна и в однопроцессорной системе, так как реализует совмещение во времени выполнение различных частей разных задач. Для такого совмещения лишь необходимо, чтобы однопроцессорная система состояла из относительно независимых, автономных частей, каждая из которых может выполнять свою работу одновременно с работой других. При этом каждая задача все-таки будет решаться последовательно, но разные части вычислительной системы будут одновременно работать над разными задачами, не мешая друг другу.
В вычислительных системах, содержащих несколько обрабатывающих устройств, возможен другой тип параллелизма: одновременное решение различных задач или одновременное решение независимых ветвей одной задачи.
Если в систему поступает непрерывный поток не связанных между собой задач (т. е. таких задач, для которых характерно, что решение любой задачи не зависит от результатов решения других задач), использование нескольких обрабатывающих устройств позволяет совместить решение этих задач во времени. Это - "естественный параллелизм независимых задач".
При решении большой задачи в ней так же могут быть выделены отдельные независимые части - ветви, которые при наличии нескольких обрабатывающих устройств могут выполняться параллельно и независимо друг от друга. Это - "параллелизм независимых ветвей".
Для естественного параллелизма независимых задач и параллелизма независимых ветвей наиболее наглядной формой графического представления является ярусно-параллельная.
Ярусно-параллельный граф представляет вычислительный процесс в виде совокупности ветвей, расположенных в нескольких уровнях (ярусах). Ветви обозначаются кружками с цифрами внутри. Длина ветви характеризуется цифрой, стоящей около кружка. Стрелками показаны входные данные и результаты обработки. Входные данные обозначаются символами "x", выходные - символами "y". Индексы при "y" есть нижние и верхние. Верхние индексы соответствуют номеру ветви, при выполнении которой получен данный результат. Нижний индекс обозначает порядковый номер результата, полученного при реализации данной ветви программы.
Ветви каждого яруса не связаны друг с другом, т.е. результаты решения какой-нибудь ветви данного яруса не являются входными данными для другой ветви этого же яруса.
На примере ярусно-параллельных графов можно выявить преимущества вычислительных систем, имеющих несколько обрабатывающих устройств, и проблемы, возникающие в таких системах.
Рассмотрим возможности ярусно-параллельного графа на примере параллелизма независимых ветвей одной задачи. Пусть необходимо в параллельной системе произвести вычисление по формуле:
и определить продолжительность вычислений по сравнению с однопроцессорной системой. Будем считать, что сложение и вычитание выполняются за 100 единиц времени, умножение - за 600, деление - за 1000.
В однопроцессорной системе последовательность действий может быть такая:
№ |
Действие |
Время |
1 |
600 | |
2 |
100 | |
3 |
100 | |
4 |
1000 | |
5 |
600 | |
6 |
600 | |
7 |
100 | |
|
Итого: |
3100 |
Время на выполнение такой последовательности действий составляет 3100 единиц.
При наличии нескольких процессоров последовательность действий может измениться (рис.16.8):
Рис. 16.8. Пример 1 ярусно-параллельного графа
сначала вычисляется
затем на разных процессорах одновременно вычисляется:
на одном из процессоров вычисляется
затем опять на любом процессоре вычисляется
и наконец, вычисляется последняя разность .
Здесь цифры обозначают ярусы.
Продолжительность операции на 1 ярусе - 600 единиц, на втором - тоже 600 (сложение и вычитание закончатся раньше, но критическим для яруса является умножение), на третьем ярусе - 1000 единиц, на четвертом - 600, и на пятом - 100. Итого t1 = 2900 единиц.
Можно самую длинную операцию 2 яруса перенести на 3 ярус. Тогда граф изменится (рис.16.9), ветвь 4 со 2-го яруса переместится на 3.
Рис. 16.9. Пример 2 ярусно-параллельного графа
В этом случае продолжительность 2 яруса станет 100, т.е. уменьшится на 500 единиц, и общее время вычислений станет равным 2400 единиц.
В случае естественного параллелизма независимых задач и большом числе задач ярусно-параллельный граф становится значительно сложнее и допускает значительно большее количество вариантов, как например, на рис.16.10.
Для такого графа характерно, что выигрыш во времени может существенно колебаться в зависимости от последовательности выполнения ветвей каждым обрабатывающим блоком (процессором), поэтому каждый процессор должен выбирать новую ветвь с учетом этого обстоятельства. Перед началом выполнения очередной ветви каждый процессор должен иметь информацию о готовности данных для этого.
Рис. 16.10. Пример 3 ярусно-параллельного графа
Таким образом, чтобы с помощью нескольких обрабатывающих устройств решить задачи, имеющие независимые параллельные ветви, необходима соответствующая организация вычислительного процесса, которая будет определять пути решения задач и вырабатывать необходимую информацию о готовности каждой ветви.
При этом возникают следующие трудности:
длительность каждой ветви известна недостаточно точно;
трудно избежать некоторых простоев из-за неготовности данных для выполнения той или иной ветви;
есть сложности и в оптимизации выделения независимых ветвей. Наличие этих трудностей несколько снижает выигрыш в производительности системы.
Однако при решении многих сложных задач одно только программирование с выделением независимых ветвей уже позволяет существенно сократить время решения.
Хорошо поддаются параллельной обработке такого типа задачи матричной алгебры (в том числе - и компьютерной графики), линейного программирования, спектральной обработки сигналов, преобразования Фурье, задачи кластерного анализа, математической статистики, автоматической классификации, и т.д.
Лекция 17