image

Безблокировочная хеш-таблиця — це медалі дві сторони. В деяких випадках вони дозволяють досягати такої продуктивності, якої не отримати іншими способами. З іншого боку, вони досить складні.

Читати далі →

image

У цьому пості ми хотіли б ще раз підняти тему програмування без блокувань, спочатку давши йому визначення, а потім виділити з усього різноманіття інформації кілька ключових положень. Ми покажемо, як ці положення співвідносяться між собою, за допомогою блок-схем, а потім ми трохи торкнемося деталей. Мінімальна вимога до розробника, постигающему lock-free, — вміння писати правильний багатопотоковий код, використовуючи м'ютекси або інші високорівневі об'єкти синхронізації, наприклад, семафори або події.

Читати далі →

Логіка свідомості. Частина 11. Природне кодування зорової і звукової інформації

У попередньої частини були сформульовані вимоги до процедури універсального узагальнення. Одна з вимог наголошувала, що результат узагальнення повинен не просто містити набір понять, крім цього отримані поняття зобов'язані формувати певний простір, в якому зберігаються уявлення про те, як отримані поняття співвідносяться між собою.

Якщо розглядати поняття як «точкові» об'єкти, то таку структуру можна частково описати матрицею взаємних відстаней і представити у вигляді зваженого графа, де вершини — це поняття, а кожному ребру зіставлено число, що відповідає відстані між поняттями, які це ребро з'єднує.

Ситуація дещо ускладнюється, коли поняття мають природу множин (малюнок нижче). Тоді можливі формулювання типу: «поняття C містить поняття A і B», «поняття A і B різні», «поняття A і B мають щось спільне». Якщо покласти, що близькість визначається в інтервалі від 0 до 1, то про малюнок зліва можна сказати: «близькість A і C дорівнює 1, близькість B і C дорівнює 1, близькість A і B дорівнює 0).

Читати далі →

Трохи Intel Xeon Phi тепер може отримати кожен

Intel Xeon Phi — унікальний процесор, як ніхто інший, розкриває всі переваги паралельного виконання завдань. Створений за технологією Intel Many Integrated Core (MIC), він надає вам кілька десятків потужних обчислювальних ядер і порядний шмат інтегрованої високошвидкісної пам'яті. Думаю, що багато програмісти, як початківці, так і досвідчені, хотіли б «поганяти» свій код на такому процесорі, щоб знайти його вузькі місця, оцінити вплив паралелізму на продуктивність і так далі. Зупиняє одне: вартість самої молодшої моделі Xeon Phi становить $2500, і це тільки сам процесор. Навряд чи багато хто ризикнуть придбати таку систему для особистих потреб, а потреба така, як вже говорилося, буває.

Тепер життя ентузіастів стає трохи простіше. Освітній центр Colfax Research за фінансової підтримки Intel запустив програму віддаленого доступу до кластера серверів на базі Intel Xeon Phi. Деталі програми — під катом, але спочатку коротко про сам Intel Xeon Phi — давненько ми на цю тему не писали.

Читати далі →

Логіка свідомості. Частина 10. Завдання узагальнення

В принципі, будь-яка інформаційна система стикається з одними і тими ж питаннями. Як зібрати інформацію? Як її інтерпретувати? В якій формі і як її запам'ятати? Як знайти закономірності в зібраної інформації і в якій формі їх записати? Як реагувати на інформацію, що надходить? Кожний з питань важливий і нерозривно пов'язаний з іншими. У цьому циклі ми намагаємося описати те, як ці питання вирішуються нашим мозком. У цій частині йтиметься про, мабуть, самої загадкової складової мислення — процедурі пошуку закономірностей.

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

Завдання узагальнення – це ключове завдання у всіх дисциплінах, які хоч якось пов'язані з аналізом даних. Математична статистика, машинне навчання, нейронні мережі – все це обертається навколо задачі узагальнення. Природно, що і мозок не залишився осторонь і як ми можемо іноді спостерігати на власному досвіді, теж часом непогано справляється з узагальненням.

Читати далі →

Що якщо в іграх використовувати видеокарточку для фізики, а не для графіки

Хочу розповісти спільноті про проведеному мною експерименті.

Мені завжди подобалися ігри, в яких є фізика. Тобто, деякі процеси не управляються скриптами, а еволюціонують у часі, слідуючи фізичним законам. З цього випливають складність і непередбачуваність ігрового процесу.

Прикладів багато, фізичні елементи тонко пронизують різноманіття комп'ютерних ігор. Взяти хоч будь-платформер: зовсім інші відчуття від гри, коли є інерція персонажа, ковзання, тяжкості, втрат від падіння великої висоти і віддача від зброї.

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

Або ще чудовий приклад — Kerbal Space Program. Там фізика вже є непосредственым джерелом геймплея.

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

Я давно мріяв зробити саме такий, до межі фізично реалістичний рімейк Scorched Earth. Але всі мої експерименти з моделюванням фізичних систем упиралися в невблаганно повільні процесори. Тисяча-дві частинок були межею для real-time симуляції.

Але недавнє моє «відкриття» змінило ситуацію.
Читати далі →

Конкурс GraphHPC-2017 на найшвидшу реалізацію завдання Betweenness Centrality


Лабораторія DISLab ВАТ «НИЦЭВТ») спільно з НИВЦ МДУ проводять четверту щорічну науково-практичну конференцію з проблем паралельної обробки великих графів з використанням суперкомп'ютерних комплексів і кластерних систем.
Мета конференції — залучення уваги до тематики завдань по суперкомпьютерной обробки графів та надання майданчика для спілкування розробників технологій суперкомпьютерной обробки графів і розробників графових додатків, обговорення перспектив даного напрямку.
Зовсім скоро, в рамках даної науково-технічної конференції GraphHPC-2017, стартує конкурс GraphHPC, присвячений проблемам паралельної обробки великих графів з використанням суперкомп'ютерів. На цей раз учасникам належить отримати найшвидшу реалізацію завдання Betweenness Centrality (Центральність з посередництва) в неориентированном графі.
Читати далі →

Як перебрати всі перестановки і про факториальном розкладання натуральних чисел

Задачі про переборі всіх можливих перестановок заданого безлічі сутностей виникають у програмуванні досить часто. Як відомо з комбінаторики, число можливих перестановок n предметів одно просто факториалу числа n

n! = n * (n — 1) * (n– 2) *… * 3 * 2 * 1

Факторіал – досить швидко зростаюча функція, про це говорить її асимптотика (формула Стірлінга), хоча досить подивитися на факториалы декількох перших членів натурального ряду:

1! 1
2! 2
3! 6
4! 24
5! 120
6! 720
7! 5 040
8! 40 320
9! 362 880
10! 3 628 800
11! 39 916 800
12! 479 001 600
13! 6 227 020 800
14! 87 178 291 200
15! 1 307 674 368 000

Як видно, факторіал 13-ти вже не вміщується в тип даних long.

Якщо задатися метою знайти однозначну відповідність між номером перестановки — числом в діапазоні від 1 до n! – і її реалізацією, можна натрапити на один дуже цікавий математичний факт.

Читати далі →

Порівняння Lock-free алгоритмів — CAS і FAA на прикладі JDK 7 і 8

Багато ядер не буває
Атомарні операції (atomics), наприклад, Compare-and-Swap (CAS) або Fetch-and-Add (FAA) широко поширені в паралельному програмуванні.

Мульти — або багатоядерні архітектури встановлені однаково як в продуктах настільних і серверних комп'ютерів, так і у великих центрах обробки даних і суперкомп'ютерах. Приклади конструкцій включають Intel Xeon Phi з 61 ядрами на чіпі, який встановлений в Tianhe-2, або AMD Bulldozer з 32 ядрами на сайті, розгорнутих в Cray XE6. Крім того, кількість ядер на кристалі неухильно зростає і процесорів з сотнями ядер, за прогнозами, будуть виготовлені в осяжному майбутньому. Спільною рисою всіх цих архітектур є зростаюча складність підсистем пам'яті, що характеризується кількома рівнями кеш-пам'яті з різними політиками включення, різними протоколами когерентності кеш-пам'яті, а також різними мережевими топологіями на чіпі, що з'єднують ядра і кеш-пам'ять.
Практично всі такі архітектури забезпечують атомарні операції, які мають численні застосування в паралельному коді. Багато з них (наприклад, Test-and-Set) можуть бути використані для реалізації блокувань та інших механізмів синхронізації. Інші, наприклад, Fetch-and-Add Compare-and-Swap дозволяють будувати різні lock-free і wait-free алгоритми і структури даних, які мають більш міцні гарантії прогресу, ніж блокування на основі коду. Незважаючи на їх важливість і повсюдне вживання, виконання атомарних операцій повністю не проаналізовано досі. Наприклад, на загальну думку, Compare-and-Swap йде повільніше, ніж Fetch-and-Add. Тим не менш, це всього лише показує, що семантика Compare-and-Swap вводить поняття «wasted work», в результаті – більш низька продуктивність деякого коду.
Читати далі →

Програмування багатоядерних DSP-процесорів TMS320C66x з використанням OpenMP

В статті описано підхід до програмування багатоядерних сигнальних процесорів на основі OpenMP. Розглядаються директиви OpenMP, розбирається їх зміст і варіанти використання. Робиться акцент на цифрових сигнальних процесорах. Приклади застосування директив OpenMP обрані наближеними до задач цифрової обробки сигналів. Реалізація проводиться на процесорі TMS320C6678 фірми Texas Instruments, що включає 8 DSP-ядер. У частини I статті розглядаються основні директиви OpenMP. У II частині статті планується доповнити список директив, а також розглянути питання внутрішньої організації роботи OpenMP і питання оптимізації програмного забезпечення.

Дана стаття відображає лекційно-практичний матеріал, пропонований слухачам в рамках курсів підвищення кваліфікації за програмою «Багатоядерні процесори цифрової обробки сигналів C66x фірми Texas Instruments», які проводяться щорічно в Рязанському радіотехнічному університеті. Стаття планувалася до публікації в одному з науково-технічних журналів, але в силу специфіки розглянутих питань було прийнято рішення про накопичення матеріалу для навчального посібника з багатоядерним DSP-процесорів. А поки даний матеріал буде збільшуватись, він цілком може полежати на сторінках Інтернету у вільному доступі. Відгуки та побажання вітаються.

Читати далі →