Обробкою даних керує одна програма простір є глобальним для програміста є одна єдина пам’ять а адеталі структури даних доступу до пам’яті І міжпроцесорного обміну для програміста скриті. слаба синхронізація обчислень на II процесорах

Вид материала

Документы

Содержание Розробка паралельного алгоритму. Планування обчислень Різні варіанти декомпозиції

Подобный материал:

• Аудиторні години 84 лекції 32, лаб роб, 55.48kb.
• Інститут комп’ютерних технологій, автоматики І метрології, 147.16kb.
• Пам'ять І навчання, 1204.53kb.
• Конспект уроку в 11 класі Тема: «Поняття баз даних. Моделі баз даних. Робота з файлами., 35.75kb.
• План Що відбувається в мозку? Організація пам'яті. З/Людська пам'ять, 63.99kb.
• Інтерфейс системи керування базами даних access. Створення бази даних. Таблиці. Запити, 156.05kb.
• Рекомендації для покращення пам'яті та уваги молодших школярів Загальні висновки, 737.37kb.
• Урок 3 практична робота №1 тема: Створення структури бази даних І введення даних, 27.48kb.
• «антирадянське кіно» леоніда гайдая людська пам'ять річ примхлива І не завжди справедлива, 639.97kb.
• Особливості пам’яті та уваги у дітей молодшого шкільного віку, 122.76kb.

Паралелізм даних

Основна ідея підходу – застосування однієї операції до кількох елементів масиву даних

(векторна і паралельна обробка)


Основні особливості підходу

• обробкою даних керує одна програма.
  
• простір є глобальним (для програміста є одна єдина пам’ять а адеталі структури даних доступу до пам’яті і міжпроцесорного обміну для програміста скриті.
  
• слаба синхронізація обчислень на II процесорах.
  
• I I операції над елементами масиву виконується на всіх допустимих даній програмі процесорах.
  

Програмування в моделі паралелізму даних спеціалізовані мови (різновидності FORTRAN)

Програміст – слабо впливає на

Найрозповсюдженішим підходом до розпаралелиння обчислень і обробки даних є підходом, що базується на моделях паралелізму даних і паралелізму задач.

В основі кожного підходу лежить розповсюдження обчислювальної роблти між доступними користувачу процесорами паралельного комп’ютера.

Проблеми:

1). Забезпечення рівномірного завантаження поцесорів.

2). Ефективна організація обміну інформації між процесорами.

Підхід базується на використанні в

Базовою роботою операцій:

• операції керування даними.
  
• опнрації над масивами та їх фрагментами.
  
• умовні операції.
  
• операції
  
• операції зсуву.
  
• операції сканування.
  
• операції пересилання даних.
  

Паралелізм задач

Метод передбачає розбитття задачі на кілька відносно самотійних задач.

(MIMD структура) – Для кожного процесора своя програма (FORTRAN чи С підхід трудоємкісний між паралелізмом даних).


Проблеми:

1. підвищена трудоємність розробки і відлагодження програм.
   
2. на – програміста – вся відповідальність за збалансоване завантаження програм.
   
3. програмісту необхідно мінімізувати обмін дними між процесорами.
   
4. підвищена небезпека виникнення тупикових ситуацй.
   

Гнучкість і свобода програміту

Спеціалізовані б-ки:

MPI (Message Passing Interface)

PVM (Parallel Virtual Machines)


Програміст контролює розподіл даних між різними процесорами і різними підзадачами, а також обмін даними.


Розробка паралельного алгоритму.


Алгоритм повинен забезпечити ефективність використати ІІ обчислювальні системи.

Необхідно піклуватись про масштабованість алгоритму (але це не просто).

1. Декомпозиція: Аналіз задачі, можливості її розпаралелиння.(Етап може бути і останній). Особливості архітектури конкретної обчислювальної системи на даному етапі не враховуються.
   
2. Проектування комунікацій: Визначаються комунікації, необхідні для пересилання вихідних даних, проміжних результатів виконання підзадач.(Вибирається алгоритм і методи комунікації.)
   
3. Укрупнення: Підзадачі об’днуються в крупніші блоки, якщо це позволить підвищити ефективність алгоритму і знизити трудоємність розробки.
   

Критерії: Ефективність алгоритму (продуктивність), і трудоємніть його реалізації.

4. Планування обчислень: Розподілення підзадач між процесорами.
   

Критерії вибору способу розміщення задач – ефективне використання процесорів з мінімальними затратами на обмін даними.


Декомпозиція.

Визначається ступінь можливого розпаралелиння задачі (менші розміри – краще).

Сегментуватися можуть як алгоритм так і дані.


Різні варіанти декомпозиції

В декомпозиціїданих спочатку сегментується дані, а потім алгоритм іх обробки.


Дані – розбиваються на фрагменти приблизно однакового розміру.

З даних і алгоритму обробки формується підзадача:

Визначаються необхідні пересилки даних: пересічення частин на які розбивається задача повинні бути зведені до мінімуму(не дублюються)


Спочатку Аналізуються структури даних найбільшого розміру або до яких частіше звертання.


Наприклад: Для сіткових методів.

Однорідне(найкрупніше розбиття)

Декомпозиція




Двохвимірни



Тьохвимірне