. Есть ли Волшебная Технология, которая все сделает сама оптимально? Хочется сказать этой технологии что-то типа «вот алгоритм, нужно его применить к этому». А оно уже там унутре вычисляет оптимальные блоки для вычитывания данных с диска, режет на куски чтоб не промазывать мимо кэша, разбрасывает обработку по CPU и т.п.

нет

Странный вопрос. Конечно же, таких решений нет и быть не может. Чем обобщённее решение, тем оно менее эффективно для конкретной узкой задачи, либо будет требовать адских ЧЧ на реализацию и отладку.

Для примера можно посмотреть на рСУБД, в частности включают ваш паттерн (т.е. ~ пробег и обработка). Движки построения планов (фактически, что и откуда нужно взять с диска, как посчитать в памяти...) выполнения пилят десятками лет, но человек всё равно ещё требуется для оптимизации этого добра под узкие задачи.

а еще аж целую книжку напейсали ISBN 978-0-470-10762-1

Есть ли Волшебная Технология...

на любой вопрос, начинающийся такими словами можно всегда смело говорить - нет

Можно еще что то из этих

главная проблема тут — костность мышления

пробегать по этой информации и делать что-то примитивное

термин «пробегать» неявно предполагает «последовательный обход», что уже само по себе не позволяет задействовать многие существующие уровни аппаратной параллельности.
Кроме того, понятие «примитивности» в современном мире процессоров существенно отличается от того же у программистов.

Потому «МапРедюс» как отправная точка обсуждения, хотя бы на уровне интерфейса этих самых «облегчающих жизнь промышленных решений» — не так уж и плохо IMHO

(с) Эдгар По (c) Николай Глазков – “Ворон"

Я спросил: - Какие в Чили
Существуют города?-
Он ответил: - Никогда!-
И его разоблачили!

А, простите, я как-то не подумал что по ссылке мало кто пойдет.

Под словами «Волшебная Технология» подразумевалось (с ирноией, если что) библиотека для С/С++ или препроцессор для него же (типа OpenMP).

Вот этот паттерн - пробежать по куче данных и выполнить над ними какую-то агрегирующую функцию - это же стандартный, э-э, паттерн?

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

Такое, наверняка, должно быть у каких-нибудь крупных обработчиков данных, или в интеле/амд, вот возможно они поделились этим?

Если это библиотека, то хотелось бы от нее получить размеры блоков, которыми нужно читать с диска, размеры блоков которые нужно обрабатывать за раз ну и еще что там нужно. Распараллелить, наверное, я смогу и сам (тем же OpenMP). Но это если уж совсем на низком уровне, может есть что-то получше?

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

Про костность мышления - это для VLev

Вы бы сходили по ссылке, почитали, что ли

Я ее посмотрел прежде чем отвечать. Из неизвестного для меня --- ISPC, и даже сам факт, что Intel поле 15 лет малопродуктивной возни с автовекторизацией озаботилась созданием удобных инструментов для векторизации.

В остальном надо понимать, что для 15-20 минутной презентации --- информации слишком много, и потому она представлена очень упрощенно.

это же стандартный, э-э, паттерн?

В том-то и дело, что эти самые «стандарты» давно пора переосмыслить, учитывая новые реалии.

В том-то и дело, что эти самые «стандарты» давно пора переосмыслить, учитывая новые реалии

Новые реалии таковы: диски очень медленные. Если вычитывать с одного диска в несколько потоков, это приведет к частым перемещениям головок и падению скорости чтения. Ну, контроллер + ОС могут что-то скорректировать, но в общем случае лучше читать последовательно. То есть параллельные чтения можно использовать только из разных источников (разных дисков или из сети). Мне это интересно очень умеренно.

PS костность мышления - это вы намекаете что надо не костным мозгом думать а головным? Тонко

Новые реалии таковы: диски очень медленные

эта реалия настолько не новая, что в прикладных программах никто и никогда непосредственно с дисков и не читает/пишет. Все обмены идут через буферы OS в RAM.
А действительно новые реалии таковы, что «диски» теперь бывают и SSD, с «чистой» латентностью (т.е. за вычетом латентности шин) не сильно большей латентности RAM.

Мне это интересно очень умеренно.

6 шт современных HDD на любом десктопном контроллере дают темп обмена более гигабайта в сек. Т.е. лишь на порядок ниже темпа обмена с RAM. То же верно для всего лишь 3 SSD.

Тонко

Честно говоря, опечатался просто. Но получилось многозначительно :)

пробежать по куче данных и выполнить над ними какую-то агрегирующую функцию

короче, если под «пробежать» и «аггрегировать» понимать свёртку (fold), то для эффективной реализации свертываемая «элементарная» функция должна позволять проводить эту свёртку деревом (tree-like fold).
Остальное --- дело техники.
В этом смысле MapReduce хорош тем, что явным образом выделяет эту часть в map.

Помню я, бабочка билась в окно.
    Крылышки тонко стучали.
Тонко стекло, и прозрачно оно.
    Но отделяет от дали.

:)

Но Тутубалин обещает при использовании правильных техник аццкий прирост производительности.

data oriented design, вот и все правильные техники

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

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

а по ISPC - это не то чтобы прямо проект Intel, думаю что это больше похоже на research или инициативу отдельных инженеров (а может и на то и на то сразу), читаем внизу

(Please note that ispc is separate from the Intel compiler products and that ispc is not supported by the regular Intel Software Support organization.)

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

for (int = 0; i < data_size; i++)
    data[i]++;

можно ускорить в несколько раз за счет загрузки сразу нескольких блоков памяти в кэш. В привёденном выше коде процессор при каждом обращении к новому блоку ждет 100500 тактов, пока он загрузится в кэш и потом обрабатывает его. Можно последовательно обращаться к сразу нескольким блокам данных, и они будут грузиться в кэш параллельно

#define BLOCK_SIZE 64

for (int = 0; i < data_size/ BLOCK_SIZE; i++)
    {
    data[i]++;
    data[i + BLOCK_SIZE]++;
    data[i + BLOCK_SIZE*2]++;
    data[i + BLOCK_SIZE*3]++;
   }

В данном примере процессор дергает 4 разных блока памяти, и ждет те же 100500 тактов загрузки уже сразу 4 блоков. Конкретные параметры (размер блока, количество возможных параллельных обращений) зависят от процессора и чипсета, 64 и 4 (по памяти, может ошибаюсь) были приведены для какого-то чипсета времен поздних P III

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

Если бы Intel это признал --- дальше было бы проще внедрять что-то другое. К сожалению, пока что он пихает ее везде где можно. gcc в частности тоже ее поддерживает теперь, хотя изначально имело чрезвычайно полезное векторное расширение типов (у Тутубалина этого, кстати — внезапно — нет).
PS: только я имею в виду именно автовекторизацию. Что касается опции --parallel, т.е. автопараллелизация циклов по типу OpenMP, то это как раз имеет право на существование как ленивое дополнение к OpenMP.

Если вычитывать с одного диска в несколько потоков, это приведет к частым перемещениям головок и падению скорости чтения.

Все то же самое относится и к памяти: последовательное чтение из нее гооораздо быстрее случайного

интересную идею оптимизации доступа к памяти

именно как оптимизация доступа к памяти --- неактуально ЕМНИП как раз со времен P-III, т.к. все более современные процессоры поддерживают аппаратную предзагрузку из памяти, причём до 8 потоков как минимум.
Конкретно по исходному коду — проще оставить как есть, любой оптимизирующий компилятор развернёт исходный цикл раз в 8, а icc еще и автовекторизацию сделает.

Так это же алхимия и есть. Круто, конечно, но

Конкретные параметры (размер блока, количество возможных параллельных обращений) зависят от процессора и чипсета

вот это убивает всю идею

Ну да ладно, похоже такие оптимизации делают только «для себя» и очень редко

Так это же алхимия и есть

именно. причём вместо золота получается как обычно дерьмо.

похоже такие оптимизации делают только «для себя»

ну почему же, я для всех делаю...

Если бы Intel это признал --- дальше было бы проще внедрять что-то другое.

интел просто старая толстая контора (которая к тому же не особо занимается системами поддерживающими массовый параллелизм), как это от её желания и пихания зависит? :)

только я имею в виду именно автовекторизацию.

это в ту же степь, что и автопараллелизация (на всякий случай: не одно и то же!) - работает неэффективно если используется только во время compile-time

последовательное чтение из нее гооораздо быстрее случайного

это конечно так, но именно «случайное» чтение никто и не предлагает.
Предлагается чисто «последовательный» доступ заменить на другой тип регулярного доступа, более подходящего к современным реалиям.
Скажем, для большинства многоядерных процессоров параллельный доступ к 2-3 разным последовательным потокам будет быстрее, чем к одному.
Что касается «алхимичности» выбора размеров блоков и т.п. для локализации данных на разных уровнях иерархии памяти, то мне это тоже не нравится.
Ну дык вместо этого можно использовать для хранения и обхода данных самоподобные структуры (скажем, бинарные деревья) --- тогда всё само локализуется где нужно.

интел просто старая толстая контора

Кроме этого Intel — локомотив всей индустрии. Потому и ошибки Intel тоже становятся общими ошибками.

массовый параллелизм

выкторизация-от-Intel это как раз пока не очень «массовый» параллелизм.
Причём пока вектор состоял всего лишь из 2-4 элементов, можно было вообще закрывать на его существование глаза (как все и делали). В этом аспекте автовекторизация при ее успехе — выглядела как приятная неожиданность.
Но теперь Intel рекламирует Xeon Phi как первый настоящий TFlops-ный чип, при этом его потенциальные покупатели как-то забывают, что невекторизованной производительности в нем в 8 раз меньше, что вполне сопоставимо с невекторизованной производительностью всего лишь двух десктопных процессоров AMD FX...

автопараллелизация... - работает неэффективно если используется только во время compile-time

Это в основном от кода зависит (как и в случае автовекторизации).
Только вот автопараллелизация поощряет программиста писать более ясный код, а автовекторизация --- более примитивный.
А это не одно и то же.

Хорошо, раз все делают вручную, расскажите, где же брать конкретные цифры?

Сколько за раз читать с диска данных?

Сколько запускать потоков для обработки этих данных? Ну, я подозреваю что приблизительно около количествава ядер, но хочется аргументированной конкретики

Какой должен быть размер изменяемого куска памяти (в который агрегируется)?

Что еще нужно учесть, чтоб оно как минимум не получилось тормознее решения «в лоб», без всяких этих премудростей?

Стратегии, я так понимаю, такие (в порядке возрастания сложности):

1. на размышления забить, цифры выбрать пролетарским чутьем

2. погонять тесты на доступных узлах, выбрать, опять же, чутьем, что-то среднее

3. запускать тесты на каждом узле, где предполагается установка, при изменении параметров узла тесты перезапускать

4. п.3 для старта, потом выбирать параметры динамически, основываясь на статистике за предыдущие периоды

Вот сейчас я вычитываю по 1М и последовательно это обрабатываю, то есть по п.1. Дойти до п.2 кажется почти выполнимым. Но если кто знает рабочие проекты, которые сделали Правильно - ткните, пожалуйста, очень хочется посмотреть.

Да, инсталляций планируется несколько десятков, как минимум

Но теперь Intel рекламирует Xeon Phi как первый настоящий TFlops-ный чип, при этом его потенциальные покупатели как-то забывают

Разве его уже можно купить?

невекторизованной производительности в нем в 8 раз меньше, что вполне сопоставимо с невекторизованной производительностью всего лишь двух десктопных процессоров AMD FX...

Как я понял интеловы MKL, IPP вроде как будут его поддерживать из коробки. Если так, то работать на нем намного приятнее чем с GPU.

Кроме этого Intel — локомотив всей индустрии.

простите, я немного запутался - мы про какую индустрию сейчас?

массовый параллелизм

выкторизация-от-Intel это как раз пока не очень «массовый» параллелизм.

да интел вообще не занимается такими системами, я, к примеру, что-то не вижу тут компании интел

Только вот автопараллелизация поощряет программиста писать более ясный код, а автовекторизация --- более примитивный.

насчёт автопараллелизации не знаю, а насчёт автовекторизации готов поспорить, не «более примитивный», а всего то навсего data centric, разве это автоматически означает примитивность?

да интел вообще не занимается такими системами, я, к примеру, что-то не вижу тут компании интел

http://i.top500.org/stats/details/procgen/1350 так виднее?

Разве его уже можно купить?

первые тыщ десять плат уже продали.
правда, злые языки утверждают, что по цене всего лишь $400 за плату.

MKL, IPP

да, а также OpenMP, MPI и проч.

работать на нем намного приятнее чем с GPU

это вопрос привычки. Я, кстати, совсем не против Phi за $400 :gigi:
но вот если он будет стоить как оценивают $2500, то ну его нафиг — десктопные видеокарты нам не изменят ;)

мы про какую индустрию сейчас?

про IT, небольшая часть которой --- разработка софта.

да интел вообще не занимается такими системами

Intel — локомотив, а не поезд.
Конкретно по Top500: Intel в 1997г построила ASCI Red http://i.top500.org/system/3059, который определил архитектуру суперкомпьютеров на следующие 15 лет как однородных кластеров, в узлах которых стоят процессоры, аналогичные десктопным.
Как раз сейчас мы наблюдаем смену базовой архитектуры суперкомпьютеров к гетерогенным системам. У GPGPU первый блин получился комом, потому вперед временно вырвался IBM c BlueGene/Q, который не совсем гетерогенный, но зато иерархический.
Intel, играясь Atom-ами, с Xeon Phi запоздал года на 2, но первый компьютер в top500 уже есть это Discovery на 150 месте http://i.top500.org/system/177816

готов поспорить

давайте.

data centric, разве это автоматически означает примитивность?

нет конечно, автоматически — не означает.
Однако, если под «data centric» подразумевать SOA, как нам во первых строках советует Intel, то таки означает, ибо мы лишаемся списков, хэш-таблиц, всевозможных деревьев и прочего, наработанного программистами за последние 55лет после появления FORTRAN-а с его common-блоками.

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

совсем не против Phi за $400 :gigi:

но вот если он будет стоить как оценивают $2500, то ну его нафиг

Да по 400 офигеть дайте две. 2500 сопоставимо с теслой с2075, так что наверное это вполне правдоподобная цена.

первые тыщ десять плат уже продали

Я так понял только по большой дружбе техасскому компьютерному центру. На базаре для всех пока нет :(

LAN-приятное исключение из общего правила

про ssd автор забыл.

а существуют ли облегчающие жизнь промышленные решения?

о них всю презентацию и рассказывалось

да интел вообще не занимается такими системами, я, к примеру, что-то не вижу тут компании интел

http://i.top500.org/stats/details/procgen/1350 так виднее?

да-да, а ручки для шкафов сделал дядюшка Чуюнг-Вонг, он теперь тоже суперкомпьютерами занимается?

мы про какую индустрию сейчас?

про IT, небольшая часть которой --- разработка софта.

ну при таких тематических ограничениях и разговор про администрирование freebsd - не оффтопик, слишком общо

PS и Intel тут снова не то что бы локомотив

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

ну то есть вот IBM с сотнями систем - это какие-то дятлы безродные, а вот Intel, сделамши пару систем - определили, понимаешь, архитектуру на века, ну-ну :)

повторюсь: Intel на рынке больших и толстых систем - представлен чуть более чем никак, это в отличие от того же IBM, которые львиную долю прибыли получает именно оттуда, у Intel в данной сфере банально нет опыта, их компетенция - десктопные процессоры

также напомню:

"Anyone can build a fast CPU. The trick is to build a fast system." Seymour Cray 

Однако, если под «data centric» подразумевать SOA

SOA = Service Oriented Architecture?

ибо мы лишаемся списков, хэш-таблиц, всевозможных деревьев

тяжело Вам там, у нас тут попроще, никто ничего не отнимает

Аналогично и с базовыми управляющими конструкциями — в нашем распоряжении лишь самые простые циклы из середины прошлого века

собственно, не могли бы Вы перечислить, пожалуйста, сложные управляющие конструкции начала этого века, чтобы я понимал о чём мы сейчас говорим

слишком общо

Я могу сказать и очень конкретно: индустрией движет закон Мура, а Intel «лишь» обеспечивает выполнение этого закона точно и в срок.
И если через два года по той или иной причине не будут выпущены новые процессоры, «гораздо лучшие» сегодняшних — администраторы freebsd почувствуют это на своей шкуре.

IBM с сотнями систем - это какие-то дятлы безродные

Ну почему же, IBM весьма достойная компания, кстати, в прошлом году 100 лет исполнилось. Перфокарту изобрели, персоналки в большой мир выпустили, и до сих пор выпускают мейнфреймы. :)

у Intel в данной сфере банально нет опыта, их компетенция - десктопные процессоры

такое впечатление, что Вы где-то проспали лет 10. :)

SOA = Service Oriented Architecture?

упс, subj-евая презентация, стр 14. SOA — Structure of Arrays.

у нас тут попроще, никто ничего не отнимает

Ну и как же автовекторизуются эти структуры?
Хотелось бы узнать отдельно про каждую из перечисленных.

сложные управляющие конструкции начала этого века

если говорить о замене именно простых циклов, то это ядра из cuda.
Впрочем, я имел в виду более распространенные конструкции объектно-ориентированных и функциональных языков.

где же брать конкретные цифры?

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

Вот сейчас я вычитываю по 1М

сейчас этого мало. Хватает разве что для одиночного SSD.
Для единичного hdd по вышеприведенной формуле, получаем 10мсек*200MB/сек*3.14~=6MB, для RAID-а еще и на число дисков умножить.

Сколько за раз читать с диска данных?

IMHO, существенную долю от размера свободной оперативной памяти. Я обычно читаю пару гигабайт (у нас на компьютерах стоит от 8GB).
Но вообще тут главное не «сколько читать» (как видите, диапазон достаточно большой, как минимум от 10МБ до 1ГБ), а «как хранить» на диске.

Сколько запускать потоков для обработки этих данных?

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

Какой должен быть размер изменяемого куска памяти (в который агрегируется)?

и еще один «неправильный» вопрос :) размер куска не так важен (тем более, что это определяется задачей), как паттерн его заполнения (т.е. организацией данных и алгоритмов).

Что еще нужно учесть

Я бы начал с определения вычислительной сложности алгоритма. Если он действительно линейный по данным, хранящимся на диске, то темп обработки просто равен темпу чтения с диска, т.е., в зависимости от организации дисковой подсистемы от 0.1 до 1GB/сек, и при размене данных в несколько TB время обработки одного запроса никак не меньше часа. И всё остальное вообще не важно, а вожно либо сократить число запросов (скажем, объединяя их в одни), либо менять алгоритм (скажем, вводя какое-то предварительное индексирование хранящейся информации).

индустрией движет закон Мура

да-да, а ещё максимы де ларошфуко, законы мёрфи и наставления по физическому развитию дошкольников

такое впечатление, что Вы где-то проспали лет 10

и что же я такого проспал?

у нас тут попроще, никто ничего не отнимает

Ну и как же автовекторизуются эти структуры?
Хотелось бы узнать отдельно про каждую из перечисленных.

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

как сделать список на базе массива - вопросов, надеюсь, нет? а вот нужны, к примеру, деревья - берём Array Compacted Trees - очень быстро, очень качественно, нужны хэши - берём те же самые деревья, только вместо ключей используем хэши и т.д.

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

ну так какие?

у Intel в данной сфере банально нет опыта, их компетенция - десктопные процессоры

Это бред. Из 346 систем из топ 500 на интеле.

Это бред. Из 346 систем из топ 500 на интеле.

эти системы делал Intel?

их компетенция - десктопные процессоры

Интел вообще системами не сильно занимается. Это не их компетенция.

Интел вообще системами не сильно занимается. Это не их компетенция.

ну вот я про это и говорю, так что фраза «Intel — локомотив всей индустрии» на мой взгляд выглядит несколько натянутой

// про десктопные процессоры - загнул конечно, но считайте то гиперболой

ну вот я про это и говорю, так что фраза «Intel — локомотив всей индустрии» на мой взгляд выглядит несколько натянутой

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