Еще о RAM, HDD, CPU-кэшах и производительности

как сделать список на базе массива - вопросов, надеюсь, нет?

учитывая, что адресное пространство линейно — у меня нет вопросов как сделать на базе массива любую хранимую в памяти структуру.

да точно так же как и обычные массивы, например

а вот с этого места поподробнее, pls Давайте попробуем вместе автовекторизовать обычную реализацию метода PIC, что-то вроде:

void cell::step(float dt) {
  calc_fields(dt);
  prepare_list4cur_step();
  pt* p=pts_lst->first();
  while(p) {
    pt* next=p->next();
    p->acc(dt, this);
    cell* cur=this,* pre=0; float pt_dt=dt;
    do { pre = cur; cur = p->mov(pt_dt, cur); } while(cur);
    pre->add2moved(p);
    p=next;
  }
  prepare_list4next_step();
}

Чипсет тоже интеловский. По крайней мере у айбиэмщиков на хеоновых серверах.

ксеоновые серваки (x-series) - это для тех у кого нет денег :)
нормальные «посоны» выбирают i-series, p-series или z-series

Так что вполне себе локомотив.

ну и какие у того локомотива решения есть для HPC?

как сделать список на базе массива - вопросов, надеюсь, нет?

учитывая, что адресное пространство линейно — у меня нет вопросов как сделать на базе массива любую хранимую в памяти структуру.

отлично, тут договорились :)

Давайте попробуем вместе автовекторизовать обычную реализацию метода PIC, что-то вроде: ... как должен быть организован список частиц в ячейке pts_list чтобы цикл while по нему icc мог автовекторизовать?

поскольку я не спец в icc и в его автовекторизаторе, то я позволю себе взять небольшой тайм-аут, для изучения вопроса

Я как-то поздно заметил это обсуждение, поэтому отвечаю с опозданием. И на замечания и по сути. 1) Про SSD - хорошее, годное замечание. Завтра я показываю эту презентацию в mail.ru - добавлю. 2) Про векторные типы. Мои эксперименты с gcc 4.6 показали, что с векторными типами не очень все здорово. Нет, понятно, простейшие операции вроде a=b+c распознаются хорошо (код получается нормальным), а вот как только чуть сложнее - и легко получить проигрыш относительно скалярного векторизованного варианта (если он векторизуется). В llvm/clang - получше. Может быть в gcc 4.7 тоже стало получше.

По исходному вопросу. Готовых фреймворков для Map/Reduce (в кластерах) - их достаточно много. Посмотрите Hadoop. Если не на кластере, а на одной машине то все же вообще просто. Относитесь к диску - как к ленте. Т.е. строго одно чтение в один момент. Какими блоками - большой разницы нет (в разумных пределах, понятно что меньше чем блок FS - не надо), ОС и покэширует и (может быть) попрефетчит. А к памяти - отнеситесь как к диску. Т.е. последовательный доступ - предпочтительнее, но если нужны структуры данных сложнее чем просто массив, то берите что-то с хорошей локальностью, вроде B-tree.

а вот как только чуть сложнее - и легко получить проигрыш относительно скалярного векторизованного варианта

эээ, я не считаю векторные типы альтернативой автопараллелизации (почему --- писал выше). Но векторные типы и их поддержка компилятором --- это прямая альтернатива интринсикам. Причём простая, элегантная и очень естественная.

Может быть в gcc 4.7 тоже стало получше.

По моему опыту существенно ничего не менялось уже лет 5. единственное что стало лучше --- это декларации поддержки операций типа scalar <op> vector правда самой поддержки во float-ах я пока не обнаружил.

В любом случае --- меня очень удивило подробное обсуждение в презентации ISPC, и полное замалчивание векторных типов.

Кстати об ISPC --- что она из себя представляет на самом деле? Примеры в презентации на первый взгляд какие-то перетяжелённые по синтаксииу.

Векторные типы:

1) да, кажутся заменой интринсинкам в теории. На практике - шаг в сторону и там где я бы воткнул mm_blend_ps - что воткнет компилятор совершенно непонятно. Производительность кода полученного из gcc бывает феноменально низкой.

2) Совместимость (многоплатформенность). 11-й интел поддерживал их только на Linux (но не на винде), MSVC - вовсе не поддерживал. И как жить?

ISPC - это попытка придумать «SIMD-C». Он совершенно клевый на тех задачах, которые на эту парадигму ложатся (к примеру, map/reduce на больших массивах скалярных данных). Ну и совершенно негодный - если не ложатся (скажем, если у вас в SIMD-векторе четверки-пиксели r,g,b,alpha - то пользоваться неудобно). Перетяжеленность там есть, версия 1.0 была проще и легче, но и возможностей было меньше.

там где я бы воткнул mm_blend_ps - что воткнет компилятор совершенно непонятно

декларируется поддержка
__builtin_shuffle (a, mask)
и
__builtin_shuffle (a,b, mask)
я, правда, до сих пор этого не использовал, хотя мне это нужно.

2) Совместимость

как концепция векторизованные типы передают самую суть SIMD, и потому совместимы практически со всем, кроме автовекторизации, включая и OpenCL.
ну а как конкретное расширение языка в gcc — ну дык пусть кто-то (тот же Intel) придумает что-то лучшее, я не против. интринсики-то intel-овские практически стандарт для векторизации.

Ну и совершенно негодный - если не ложатся (скажем, если у вас в SIMD-векторе четверки-пиксели r,g,b,alpha - то пользоваться неудобно)

жаль.

С концепцией - я не спорю, концепция нормальная. Проблема в имеющихся реализациях. Повторю еще раз:

1) «Linux only». В том смысле, что gcc/clang/ intel C++ на Linux. Наверное, еще на маке есть, не смотрел. Виндов - нет (даже Intel C++/Win32 не поддерживал когда я смотрел).

2) У gcc - проблемы с производительностью в некоторых случаях. И разборки с ней занимают больше времени и сил, чем просто на _mm* все написать.

3) У gcc - взятый из доки пример скомпилировался gcc, но не компилировался g++ (т.е. в C++-режиме). С учетом первых двух проблем - я не стал разбираться дальше, может и можно в C++ это запихать.

И ровно по этим трем причинам (хватило бы любой из первых двух) - про это нет ни слова в обсуждаемой презентации.

Есть и четвертая - я и так в регламент выступления на HL++ вписался с огромным скрипом (не с первого прогона), кроме векторных типов (про которые я знаю) там много всего хорошего еще пришлось выкинуть/сократить/убрать в доп-материалы (скажем, про компиляторную автовекторизацию, которая в реальной жизни - актуальнее).

Завтра с этой же презентацией выступаю еще раз, там времени будет больше, про векторные типы - упомяну, но с оговоркой что лично у меня приготовить этих кошек не получилось.

По мне, так если мы уж начинаем рефакторить программу для использования векторизации (векторных команд), так надо сразу до intrinsics идти (или до ассемблера), работы практически столько же, а гадать что там компилятор учудил - не придется. Если бы он чудил без просадки производительности (иногда - в разы), было бы проще. Вот ISPC в этом смысле хорош - если он не нажаловался, что исходник ему не нравится - то код будет хороший.

Ну а чего жаль - там парадигма другая («программируем одну SIMD lane»)

RGBA ложится на _mm* напрямую, там вообще же все клево и удобно.

Проблема в имеющихся реализациях

с этим как раз я не спорю, но кто-то же должен взять на себя разработку и продвижение «беспроблемной» реализации. Потому как и у всех альтернативных решений есть свои проблемы.

Linux only

поскольку я занимаюсь численным моделированием — конкретно мне этого более чем достаточно. Кстати, я не знал, что векторные типы поддерживаются icc и clang

У gcc - проблемы с производительностью в некоторых случаях

IMHO, это не связано конкретно с векторизацией, это скорее общие проблемы с оптимизацией

Я кстати посмотрел пример про оптимизацию матричного преобразования цвета - там как раз и надо использовать __builtin_shuffle

если мы уж начинаем рефакторить программу для использования векторизации (векторных команд), так надо сразу до intrinsics идти

subj-евая презентация, слайд 12 «Под что код делать будем»? Кстати, последняя прекрасная иллюстрация в этом смысле — FMA, ускоряющая fp код вдвое (у AMD Бульдозер уже поддерживает FMA4, у Intel Haswell будет в следующем году, но FMA3), то есть любой intrinsic код для fp, разработанный ранее — можно смело выкидывать.
Кстати --- можете добавлить на этот слайд еще и Xeon Phi со своим набором команд (правда его официального названия я пока не знаю) :(

программируем одну SIMD lane

да, это как раз похоже на ядра cuda

RGBA ложится на _mm* напрямую

не, мне не RGBA нужен, но совсем короткие векторы со сложной перетасовкой компонент. Я месяц пытался написать этот код на интринсик-ах, но потом плюнул до появления какой-то новой технологии.

Да, я согласен, потенциальная переносимость путем перекомпиляции - это хороший и правильный аргумент в отношении распространяемой в исходниках программы (не суть важно, опенсорц или по месту компилируем). Ну значит пусть чинят так или иначе. По состоянию на год назад - это не годилось.

Я как-то поздно заметил это обсуждение

Это у вас, наверное, крибрум сбоил? :-)

на одной машине то все же вообще просто

Ну, я интуитивно вот это все понимаю, просто подумалось что кто-то это уже мог оформить (и заопенсорсить) в виде библиотеки или еще чего-то такого.

Минимально напрягая моск получить немного производительности против решения «в лоб» и заодно спрятать всю эту низкоуровневую магию подальше (ну и снять с себя заботу об оптимизации в этом месте) - было бы здорово.

Наверное, что-то типа «mmap с особенностями» смотрелось бы вполне нормально.

Впрочем, ладно, нет готового и ничего страшного.

Спасибо что откликнулись.

не, не крибрум. Надо, действительно, подписаться там, а то че это я.

Возвращаясь к вашему вопросу. 1) «На многих машинах» - есть какое-то количество готовых фреймворков. Hadoop - самый известный, вообще же их должно быть много.

2) На одной машине - много ядер (работаем в памяти) - Intel TBB вполне такая библиотека, как вы хотите (если я правильно понимаю чего вы хотите).

3) На одной машине, но ограничивает скорость диск. Тут много не придумаешь, главное чтобы не было параллельных запросов к диску, дергающих головой. Ну значит по одному потоку на диск, чтобы читали (или aio) и обрабатывать. Непонятно, какой библиотеки вы хотите?