Лабораторные работы по информатике

Практикум по физике Лабораторные работы по информатике Microsoft Visio Алгоритмические основы машинной графики AutoCAD
Практикум по механике и молекулярной физике
ОПРЕДЕЛЕНИЕ МОМЕНТА ИНЕРЦИИ
МАТЕМАТИЧЕСКИЙ МАЯТНИК
Физический маятник
ОПРЕДЕЛЕНИЕ МОДУЛЯ ЮНГА
ПОПЕРЕЧНЫЕ КОЛЕБАНИЯ СТРУНЫ
ОПРЕДЕЛЕНИЕ КОЭФФИЦИЕНТА ВЯЗКОСТИ
ОПРЕДЕЛЕНИЕ КОЭФФИЦИЕНТА ПОВЕРХНОСТНОГО НАТЯЖЕНИЯ
ОПРЕДЕЛЕНИЕ ВЛАЖНОСТИ ВОЗДУХА
ОПРЕДЕЛЕНИЕ АДИАБАТИЧЕСКОЙ ПОСТОЯННОЙ ВОЗДУХА
Вынужденные колебания линейного осциллятора
Лабораторные работы по информатике
Определение параметров n-мерных коммутационных структур
Преобразование последовательного алгоритма в параллельный
Представление алгоритмов в виде граф–схем.

Построение матрицы логической несовместимости операторов

Построение множеств взаимно независимых операторов
Определение ранних и поздних сроков окончания выполнения операторов
Запуск параллельных программ на кластере
Microsoft Visio
Спецификация требований к информационной системе
Основы работы в редакторе деловой графики Microsoft Visio 2010.
Лабораторная работа №3
Лабораторная работа №4
Функциональное моделирование
Диаграмма классов
Алгоритмические основы машинной графики

Анимация и морфинг

Отсечение прямоугольным окном
Построение проекции трехмерного объекта
Создание простых объектов
Основные навыки работы с объектами
Привязка объектов
Редактирование формы произвольных кривых
Приемы работы с контурами объектов
Создание цветных изображений
Обмен изображениями с другими программами
Ввод и редактирование текста
СИСТЕМА АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ AutoCAD
Основы работы с использованием системы AutoCAD
Команды рисования
Нанесение надписей
Команды редактирования
Проставление размеров на чертеже
Работа с блоками чертежа
 

Лабораторная работа №1. Определение параметров n-мерных коммутационных структур ВС типа гиперкуб, тор и циркулянт

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

Теоретическая часть

В настоящее время в индустрии ВС получили широкое распространение коммутационные структуры (КС) типа циркулянтных. Эти структуры традиционно представляются Dn-графами.

Определение 1.1. Циркулянтой называется Dn-граф, представляемый в виде множества , где N – число вершин в графе, вершины нумеруются от 0 до N-1,  – множество образующих чисел таких, что , а для чисел  наибольший общий делитель, равен 1, n – число образующих чисел. Вершина i соединяется ребрами с вершинами .

Определение 1.2. Если граф коммутационной структуры имеет равные степени вершин [1], то КС называется симметричной, и несимметричной – в противном случае.

Циркулянта относится к классу симметричных КС. Пример циркулянты, представленной в виде двумерной матрицы или хордового кольца [3] показан на рисунке 1.1 для {7,1,3}.

Рисунок 1.1. Пример циркулянты {7,1,3}, изображенной в виде двумерной матрицы (а) и хордового кольца (б)

Определение 1.3. КС типа n-мерный двоичный гиперкуб описывается следующими соотношениями:

вершины имеют номера , p=0,1,…, n-1, где n – размерность гиперкуба;

каждая вершина Vi задана двоичным числом ;

между вершинами Vi и Vj проводится ребро, если их двоичные номера q(Vi) и q(Vj) различаются только одним разрядом. На рисунке 1.2 представлены булевы кубы размерностей 2, 3, 4.

Определение 1.4. Обобщенный гиперкуб размерности n – это КС, которая удовлетворяет следующим требованиям:

по каждой координате k, k=1,…, n откладываются точки (вершины), с номерами 0,1,..., Nk-1, где Nk – размерность куба по координате k;

 

Рисунок 1.2 Пример представления схем булевых кубов размерности 2 (а), 3 (б), 4 (в)

множество вершин графа КС задается декартовым произведением ;

две вершины соединяются ребром, если декартовы произведения отличаются друг от друга для рассматриваемой точки и текущей на 1.

Для 3-х мерного куба 432 образуются точки по координатам (0,1,2,3), (0,1,2), (0,1) и соответствующие декартовы произведения:

(0,0,0), (0,0,1), (0,1,0), (0,1,1), (0,2,0), (0,2,1),

(1,0,0), (1,0,1), (1,1,0), (1,1,1), (1,2,0), (1,2,1),

(2,0,0), (2,0,1), (2,1,0), (2,1,1), (2,2,0), (2,2,1),

(3,0,0), (3,0,1), (3,1,0), (3,1,1), (3,2,0), (3,2,1).

Ребра проводятся между вершинами (0,0,0) и (0,0,1), (0,1,0), (1,0,0). Вершина (0,0,1) соединяется с вершинами (1,0,1), (0,1,1), (0,0,2) и т.д.

Пример представления этой структуры показан на рисунке 1.3.

Рисунок 1.3 Схема представления обобщенного 3-х мерного гиперкуба 4х3х2

На основе кубических структур КС введены торы (для одномерного случая – кольцевые структуры).

Определение 1.5. Структура вычислительной сети типа «двумерный тор» описывается графом , где M – множество вычислителей, , N  6, а  – состоит из множества рёбер skj,   – множество столбцов,  – множество строк и . Ребро проводится между вершинами, определяемыми декартовым произведением . Две вершины соединяются ребром, если их декартовы произведения отличаются друг от друга на 1 по любой координате или на L - 1 по координате k или на Y - 1 по координате j соответственно.

Примечание: К обобщённому двумерному тору относятся также и КС, содержащие не все рёбра, отстоящие на расстоянии Y - 1 по координате j или на L - 1 по координате k.

Другими словами можно сказать, что двумерный тор это КС типа 2D решётка, противоположные грани которой соединены, обеспечивая обмен данными между первым и последним элементами строки/столбца.

 

Рисунок 1.4. КС типа двумерный тор (а) и трёхмерный тор (б)

Так, например, из двумерной решётки, показанной на рисунке 1.4, а тор получается введением дополнительных связей, обозначенных на данном рисунке жирными линиями. Степень вершины равна 4. На рисунке 1.4, б показано построение тора со степенью вершины равной 4 из обобщённого 3D-куба (3x2x2).

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

Определение 1.3. Диаметр d – это максимальное расстояние, определяемое как

,

где dij – расстояние между вершинами i, j рассматриваемой КС.

Расстояние dij есть минимальная длина простой цепи [1] между вершинами i, j, где длина измеряется в количестве ребер между вершинами i, j. Например, на рисунке 1.1а длины между вершинами (0, 5) есть 3 ((0,1),(1,2),(2,5)), 2 ((0,1),(1,5)), 2 ((0,4),(4,5)), 3 ((0,3),(3,4),(4,5)), 3 ((0,3),(3,6),(6,5)), 2 ((0,6),(6,5)) и др., длина которых больше 3-х. Следовательно, расстояние d05 равно 2.

Определение 1.4. Средний диаметр для симметричной КС относительно выделенной вершины di определяется как

, (1.1)

где pi– расстояние от текущей вершины до выделенной (i-ой), – число вершин, находящихся на расстоянии pi от выделенной.

Формула (1.1) справедлива для определения среднего диаметра относительно любой вершины, принятой в качестве выделенной, для симметричной КС.

Определение 1.5. Для несимметричной КС средний диаметр определяется как усреднение по всем di, вычисленным по формуле (1.1), рассматриваемого графа КС:

.

Вопросы для самопроверки

Каким образом структура КС влияет на скорость работы ВС?

Чем отличается расстояние между вершинами от длины простой цепи?

Что такое циркулянта и каким образом она определяется?

Дайте определение диаметра КС и среднего диаметра.

Чем отличается изображение циркулянты в виде двумерной матрицы от хордового кольца?

Дайте аналитическое описание структуры типа двоичный n-мерный гиперкуб.

Дайте аналитическое описание двумерного тора.

Какие преимущества имеют КС типа n-мерные двоичные торы перед n-мерными двоичными кубами?

Дайте определение декартового произведения над множествами.

Дайте аналитическое описание КС типа обобщённый n-мерный гиперкуб.

Задание на лабораторную работу

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

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

Построить графики зависимостей диаметров и средних диаметров от числа вершин в графе КС.

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

Продемонстрировать работающую программу преподавателю и получить отметку о её выполнении.

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

Провести анализ полученных зависимостей.

Оформить отчет о проделанной работе.

Содержание отчета

Цель работы.

Ответы на вопросы для самопроверки.

Схема обрабатывающего алгоритма и описание его работы.

Распечатки экранных форм, полученных в результате работы программы.

Анализ полученных результатов.

Лабораторная работа №2. Преобразование последовательного алгоритма в параллельный Цель работы – ознакомление с принципами преобразования последовательного алгоритма в параллельный. Составление программы этого преобразования для соответствующего варианта задания.

Лабораторная работа №3. Представление алгоритмов в виде граф–схем. Цель работы – ознакомление с принципами организации параллельных вычислений с помощью информационного (ИГ) или информационно-логического графа (ИЛГ), представляющего алгоритм решения поставленной задачи

Лабораторная работа №4. Построение матрицы логической несовместимости операторов Цель работы – ознакомление с понятием логической несовместимости операторов, практическая реализация алгоритмов работы с матрицами логической несовместимости L в виде программных модулей.

Лабораторная работа №5. Построение множеств взаимно независимых операторов Цель работы – ознакомление с понятием множеств взаимно независимых операторов (ВНО). Вычисление матрицы ВНО. Определение множества ВНО и упорядочение его в порядке убывания.

Лабораторная работа №6. Определение ранних и поздних сроков окончания выполнения операторов и оценка снизу требуемого количества процессоров и времени решения задачи на ВС Цель работы – ознакомление с понятиями ранних и поздних сроков выполнения операторов. Практическая реализация алгоритмов нахождения этих сроков и оценки минимального числа процессоров и времени выполнения задачи, представленной заданным графом алгоритма. Вычисление оценок снизу требуемого количества процессоров и времени решения задачи, представленной заданным графом.

Лабораторная работа №7. Запуск параллельных программ на кластере Цель работы – практическая реализация и отладка простейших параллельных программ "Hello world" и вычисления числа π на кластере. Работа с очередью заданий на кластере с помощью планировщика IBM Tivoli LoadLeveler

 

Лабораторные работы