» » Параллельное программирование » Страница 15

 

Lock-free структуры данных. Concurrent maps: rehash, no rebuild

Автор: admin от 4-03-2015, 09:00, посмотрело: 426

Lock-free структуры данных. Concurrent maps: rehash, no rebuild
Пройдем по следам C++ 2015 Russia далее.
В предыдущей статье мы рассмотрели алгоритм для lock-free ordered list и на его основе сделали простейший lock-free hash map. У этого hash map есть недостаток: размер хеш-таблицы постоянен и не может быть изменен в процессе роста числа элементов в контейнере. Это не представляет проблемы, если мы заранее примерно представляем требуемый объем контейнера. А если нет?

Категория: Программирование

 

Lock-free структуры данных. Concurrent map: разминка

Автор: admin от 3-03-2015, 09:00, посмотрело: 528

Lock-free структуры данных. Concurrent map: разминка
Мне оказали честь — пригласили выступить на первой конференции C++ 2015 Russia 27-28 февраля. Я был насколько наглым, что запросил 2 часа на выступление вместо положенного одного и заявил тему, наиболее меня интересующую — конкурентные ассоциативные контейнеры. Это hash set/map и деревья. Организатор sermp пошел навстречу, за что ему большое спасибо.
Как подготовиться ко столь ответственному испытанию выступлению? Первое — нарисовать презентацию, то есть кучу картинок, желательно близко к теме. Но надо ещё и два часа озвучивать картинки, — как все это запомнить? Как избежать глубокомысленных «ээээмммм», «здесь мы видим», «на этом слайде показано», несвязных прыжков повествования и прочих вещей, характеризующих выступающего c не очень хорошей стороны в части владения родным языком (это я про русский, с C++ я разобрался быстро — никакого кода в презентации, только картинки)?
Конечно, надо записать свои мысли, глядя на слайды. А если что-то написано, то не худо бы и опубликовать. А если публиковать, — то на хабре.
Итак, по следам C++ 2015 Russia! Авторское изложение, надеюсь, без авторского косноязычия, без купюр и с отступлениями по теме, написанное до наступления события, в нескольких частях.

Категория: Программирование

 

Intel® Graphics Technology: «выгружаем» вычисления на графику

Автор: admin от 24-02-2015, 10:03, посмотрело: 562

Intel® Graphics Technology: «выгружаем» вычисления на графику

Продолжаем начатый разговор о Intel® Graphics Technology, а именно о том, что у нас есть в распоряжении с точки зрения написания кода: прагмы offload и offload_attribute для оффлоадинга, атрибуты target(gfx) и target(gfx_kernel), макросы __GFX__ и __INTEL_OFFLOAD, интринсики и набор API функций для асинхронного оффлоада. Это всё, что нужно нам для счастья. Чуть было не забыл: конечно, нам нужен компилятор от Intel и магическая опция /Qoffload.

Но обо всё по порядку. Одна из основных идей – это относительно легкая модификация существующего кода, выполняемого на CPU для его выполнения на интегрированной в процессор графике.

Категория: Программирование

 

Posix threads

Автор: admin от 23-01-2015, 13:14, посмотрело: 842

Posix threads

Рано или поздно любой программист в своей жизни встречается с многопоточностью.

Многопоточность – это свойство алгоритма распаралеливатся, т.е. выполнять операции некими вычислителями независимо друг от друга.

Самый простой пример — это программирование GUI. GUI всегда должен быть отрисован, вне зависимости от того, что делается в программе. Например, loading screen – он всего лишь показывает прогресс, по мере загрузки ресурсов. И выглядит это примерно так:

Posix threads

Для решения подобных задач используются потоки (threads). Почти каждый язык программирования содержит свой wrapper над потоками ОС, или реализует свои потоки (привет, велосипед). На Хабре есть довольно много статей про потоки, например, «Что такое нити (threads)?» или «Многопоточность в Java». В общем, поиск в помощь. Но эта статья будет отличатся тем, что здесь будут рассмотрены нативные потоки ОС – POSIX threads.

Категория: Программирование

 

Ещё раз (надеюсь, последний) про double-checked locking

Автор: admin от 16-01-2015, 13:09, посмотрело: 573

Статей про double-checked locking на Хабре было столько, что казалось бы ещё одна — и Хабр лопнет. Вот только по Java неплохие публикации: Реализация Singleton в JAVA, Правильный Singleton в Java, А как же всё-таки работает многопоточность? Часть II: memory ordering или вот замечательный пост от TheShade (слава web-archive!). В наши дни, наверно, каждый Java-разработчик слышал, что если используешь DCL, будь добр объявить переменную volatile. Найти сегодня в коде известных опенсорсных проектов DCL без volatile довольно трудно, но оказалось, что проблемы ещё не полностью решены. Поэтому я добавлю небольшую заметку по теме с примерами из реальных проектов.

Иногда складывается ощущение, что программисты не включают мозги и не пытаются понять, как что работает, а просто следуют простым и понятным правилам вроде «объяви переменную volatile, используй DCL, и всё будет хорошо». К сожалению, такой подход в программировании не всегда работает.

Категория: Программирование

 

Параллельное программирование с CUDA. Часть 2: Аппаратное обеспечение GPU и шаблоны параллельной коммуникации

Автор: admin от 10-12-2014, 18:15, посмотрело: 1333

Содержание


Часть 1: Введение.
Часть 2: Аппаратное обеспечение GPU и шаблоны параллельной коммуникации.
Часть 3: Фундаментальные алгоритмы GPU: свертка (reduce), сканирование (scan) и гистограмма (histogram).
Часть 4: Фундаментальные алгоритмы GPU: уплотнение (compact), сегментированное сканирование (segmented scan), сортировка. Практическое применение некоторых алгоритмов.
Часть 5: Оптимизация GPU программ.
Часть 6: Примеры параллелизации последовательных алгоритмов.
Часть 7: Дополнительные темы параллельного программирования, динамический параллелизм.

Категория: Программирование

 

Параллельное программирование с CUDA. Часть 1: Введение

Автор: admin от 10-12-2014, 15:22, посмотрело: 860

Еще одна статья о CUDA — зачем?


На Хабре было уже немало хороших статей по CUDA — раз, два и другие. Однако, поиск комбинации «CUDA scan» выдал всего 2 статьи никак не связанные с, собственно, алгоритмом scan на GPU — а это один из самых базовых алгоритмов. Поэтому, вдохновившись только что просмотренным курсом на Udacity — Intro to Parallel Programming, я и решился написать более полную серию статей о CUDA. Сразу скажу, что серия будет основываться именно на этом курсе, и если у вас есть время — намного полезнее будет пройти его.

Категория: Программирование

 

Lock-free структуры данных. Диссекция очереди

Автор: admin от 9-12-2014, 10:00, посмотрело: 389

Lock-free структуры данных. Диссекция очереди
Со времени предыдущего поста из жизни lock-free контейнеров прошло немало времени. Я рассчитывал быстро написать продолжение трактата об очередях, но вышла заминка: о чем писать, я знал, но реализации на C++ этих подходов у меня не было. «Не годится писать о том, что сам не попробовал», — подумал я, и в результате я попытался реализовать в libcds новые алгоритмы очередей.
Сейчас настал момент, когда я могу аргументированно продолжить свой цикл. В данной статье закончим с очередями.

Кратко напомню, на чем я остановился. Были рассмотрены несколько интересных алгоритмов lock-free очередей, а под занавес приведены результаты их работы на некоторых синтетических тестах. Главный вывод — всё плохо! Надежды на то, что lock-free подход на магическом compare-and-swap (CAS) даст нам пусть не линейный, но хотя бы какой-то рост производительности с увеличением числа потоков, не оправдались. Очереди не масштабируются. В чем причина?..

Категория: Программирование

 

Атомарные и неатомарные операции

Автор: admin от 3-12-2014, 12:31, посмотрело: 686

Атомарные и неатомарные операции

В Сети уже очень много написано об атомарных операциях, но в основном авторы рассматривают операции чтения-модификации-записи. Однако, существуют и другие атомарные операции, например, атомарные операции загрузки (load) и сохранения (store), которые не менее важны. В этой статье я сравню атомарные загрузки и сохранения с их неатомарными аналогами на уровне процессора и компилятора C/C++. По ходу статьи мы также разберемся с концепцией «состояния гонок» с точки зрения стандарта C++11.

Категория: Программирование

 

Процессоры, ядра и потоки. Топология систем

Автор: admin от 25-11-2014, 09:07, посмотрело: 961

В этой статье я попытаюсь описать терминологию, используемую для описания систем, способных исполнять несколько программ параллельно, то есть многоядерных, многопроцессорных, многопоточных. Разные виды параллелизма в ЦПУ IA-32 появлялись в разное время и в несколько непоследовательном порядке. Во всём этом довольно легко запутаться, особенно учитывая, что операционные системы заботливо прячут детали от не слишком искушённых прикладных программ.

Процессоры, ядра и потоки. Топология систем

Используемая далее терминология используется в документации процессорам Intel. Другие архитектуры могут иметь другие названия для похожих понятий. Там, где они мне известны, я буду их упоминать.

Цель статьи — показать, что при всём многообразии возможных конфигураций многопроцессорных, многоядерных и многопоточных систем для программ, исполняющихся на них, создаются возможности как для абстракции (игнорирования различий), так и для учёта специфики (возможность программно узнать конфигурацию).

Категория: Программирование, Системное администрирование