Оцінка характеристик паралелізму задач
Побудова ярусно-паралельної форми (ЯПФ) алгоритму обчислення арифметичного виразу. Оцінка основних характеристик паралелізму: довжини і ширини ЯПФ, коефіцієнту завантаження. Порівняння можливостей на n-процесорній системі в зіставленні з одно-процесорною.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | лабораторная работа |
| Язык | украинский |
| Дата добавления | 30.03.2010 |
| Размер файла | 149,0 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
кафедра математичних дисциплін та інформатики
Звіт
з дисципліни: ”ОАПСОС”
Лабораторна робота №1
на тему:
”Оцінка характеристик паралелізму задач”
ТЕРНОПІЛЬ-2008
Постановка задачі
За заданим викладачем варіантом (8 варіант) скласти ЯПФ алгоритму обчислення арифметичного виразу й оцінити основні характеристики паралелізму: довжину і ширину ЯПФ, коефіцієнти прискорення і завантаження. Число процесорів у ВР прийняти рівним ширині ЯПФ.
, та вираз
a/b + c/d + ef/(g + h) + k/m.
ЯПФ (ярусно-паралельна форма) арифметичного вираження
Дано вираз
a/b + c/d + ef/(g + h) + k/m
та , .
Нехай відомо, що процесор ВР витрачає на виконання операцій множення, розподіли і додавання часи ty, td і tc, зв'язані співвідношеннями
ty = бtc ,
td = вtc .
Без обмеження спільності можна прийняти tc = 1; тоді ty = б і td = в. Відомо також, що в > б > 1.
Використовуючи ці дані, а також визначення незалежності галузей, будуємо ЯПФ вираження
a/b + c/d + ef/(g + h) + k/m.
Вона має вид зображений на рис.1.
Рис. 1. ЯПФ.
Результати розрахунків
Розрахунки при б=2, в=4.
Ширина ЯПФ:
B = max {B0, B1, B2, B3} = max {4, 3, 1, 1} = 4 .
Знаходимо довжини всіх ярусів:
l0 = max {в, в, б, 1} = в ,
l1 = max {1, в, в} = в ,
l2 = 1 ,l3 = 1 ,
Знаходимо довжину ЯПФ:
L = l0 + l1 + l2 + l3 = 2в + 2.
Знаходимо максимальну довжину ЯПФ:
Lmax = 4в + б + 4 .
Якщо число n процесорів ВР не менше 4, то при цьому досягається мінімально можливий час рішення задачі
Lmin = L = 2в + 2,
і коефіцієнт прискорення обчислень дорівнює
,
.
Коефіцієнт завантаження при n = 4
,
.
Отже, при б=2, в=4 K = 2,4286 і с = 0,6071.
Висновки
Під час виконання лабораторної роботи була складена оцінка характеристик паралелізму задач за ярусно-паралельною формою (ЯПФ) алгоритму. Тобто побудова ярусно-паралельної форми арифметичного виразу, визначення коефіцієнта прискорення та завантаження. Побудова ярусно-паралельної форми дала нам можливість описати характеристику паралельного обчислення. Коефіцієнт прискорення - можливість побачити в скільки разів розраховується задача на n-процесорній системі в зіставленні з одно-процесорною системою. Коефіцієнт завантаження - можливість оцінити частку процесорного часу використаного на вирішення задачі.
Подобные документы
Принцип роботи конвеєрних комп’ютерних систем. Опис можливостей паралельної обробки інформації обчислювальною системою. Конвеєрна обробка на кожному з рівнів. Розширення трирівневої моделі паралелізму засобами опису потенційних можливостей конвейєризації.
лабораторная работа [44,0 K], добавлен 21.10.2014Аналіз паралельного обчислення, під яким розуміють сукупність питань, що відносяться до створення ресурсів паралелізму в процесах вирішення задачі з метою досягнення більшої ефективності використання обчислювальної техніки. Другий та третій закони Амдала.
реферат [127,2 K], добавлен 13.06.2010Програма розрахунку інформаційних характеристик каналу зв'язку. Побудова коду для передачі повідомлень. Процедури кодування, декодування та оцінка ефективності кодів. Програма на алгоритмічній мові Паскаль. Канальна матриця, що визначає втрати інформації.
курсовая работа [147,7 K], добавлен 09.07.2009Розгляд основ сучасної технології підготовки та рішення на електронних обчислювальних машинах розрахункових задач військового та прикладного характеру. Побудова блок схеми, програмної реалізації алгоритму сортування. Оцінка трудомісткості сортування.
курсовая работа [301,5 K], добавлен 08.07.2015Розгляд операційних систем MS DOS та Windows. Написання модуля обчислення умовного арифметичного виразу на мові Assembler та вбудування його виводу у програму Pascal. Виконання тестових перевірок та знаходження нормальних і аномальних результатів.
курсовая работа [1,4 M], добавлен 15.02.2010Побудова блок-схеми алгоритму проста вставка. Програмна реалізація алгоритму, опис результатів. Особливості обліку ітерації масивів. Відсортування даних за допомогою програми Turbo Pascal. Аналітична оцінка трудомісткості, графічне представлення.
контрольная работа [570,1 K], добавлен 21.05.2014Засвоєння засобів аналізу трудомісткості обчислювальних алгоритмів. Побудова графа алгоритму з отриманої блок-схеми. Мінімізація графа, його подання у вигляді стохастичної матриці. Знаходження кількості звернень до файлів за допомогою Microsoft Excel.
лабораторная работа [681,5 K], добавлен 02.06.2011Розробка алгоритму та написання програми обчислення множин. Доведення теоретико-математичних тотожностей і тверджень. Побудова диз’юнктивної нормальної форми. Розробка алгоритму та написання програми знаходження множини елементарних циклів у графі.
курсовая работа [184,4 K], добавлен 17.04.2011Значення функції, типи елементів масиву та їх кількість. Побудова інтерполяційного багаточлена Лагранжа. Апроксимування залежності багаточленом другого ступеня і обчислення коефіцієнту варіації. Обчислення рівняння за методом Рунге-Кути, лістинг програми.
контрольная работа [222,4 K], добавлен 17.02.2011Операційна система MicroDSP-RTOS, їх загальна характеристика та призначення, оцінка можливостей і інструментарій. Управління завданнями в даній операційній системі, синхронізація та взаємодія задач. Підтримка MicroDSP-RTOS в MetaDSP різними програмами.
контрольная работа [832,8 K], добавлен 21.05.2010
