Метод рекурсивну координатної бісекції для декомпозиції розрахункових сіток



Введення
Розрахункові сітки широко застосовуються при вирішенні чисельних задач за допомогою методів кінцевих різниць. Якість побудови такої сітки в значній мірі визначає успіх у рішенні, тому іноді сітки досягають величезних розмірів. У цьому випадку на допомогу приходять багатопроцесорні системи, адже вони дозволяють відразу вирішити 2 завдання:

  1. Підвищити швидкість роботи програми.
  2. Працювати з сітками такого розміру, який не поміщається в оперативній пам'яті одного процесора.
При такому підході сітка, що покриває розрахункову область, розбивається на безліч доменів, кожен з яких обробляється окремим процесором. Основна проблема тут полягає в «чесності» розбиття: потрібно вибрати таку декомпозицію, при якій обчислювальне навантаження розподілено рівномірно між процесорами, а накладні витрати, викликані дублюванням обчислень і необхідністю передачі даних між процесорами, малі.

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

Читати далі →

Переклад підручника по алгоритмах

  
 
Радий повідомити, що вийшов переклад відмінного підручника Дасгупта, Пападімітріу, Вазірані «Алгоритми», над яким я працював останні кілька років. У книзі багато алгоритми пояснені набагато коротше і простіше, ніж в інших підручниках: з одного боку, без зайвого формалізується, з іншого — без втрати математичної строгості. Відкрийте книгу на якому-небудь відомому вам алгоритмі і переконаєтеся в цьому. =)
 
Загалом, угощайтесь: друкований варіант перекладу , електронний варіант перекладу (PDF) , друкований варіант оригіналу , електронний варіант оригіналу (PDF) .
 
Читати далі →