RU>Насколько я понимаю, на сегодняшний день считается, что а) любая вычислительная система может быть промоделированная МТ, б) как следствие, любая существующая вычислительная система не мощнее (а значит _слабее_) МТ (хотя и возможно и даже скорее всего, превосходит МТ по оптимальности на некоторых задачах) и значит для теоретических нужд может быть сведена к МТ (в частности релевантная данной теме "многоленточная МТ" тоже сводится к простейшей МТ), в) лямбда-калькулис эквивалентен МТ и может быть использован как замена для теоретических выкладок. RU>Форов в лямбде нет, но есть рекурсия через Y-combinator, так что фор имплементируется элементарно... Так что я не вполне понимаю ваши опасения по поводу полноты: в любом случае любая из существующих реальных вычислительных систем-языков слабее МТ в силу "небесконечности" реальной ленты, но каждая из систем слабее с разной степенью удобства для программиста и возможного параллельного транслятора
Насчёт "слабее" — совсем не уверен. Точнее, эта проблема не кажется мне принципиальной; ясно что реальный вычислитель тратит ещё и время на каждый шаг. ИМХО, временная сложность порождает существенно больше проблем, чем пространственная. Обычно мы не можем посчитать какие-то вещи, потому что это слишком долго, а не потому, что у нас не хватает ячеек памяти для хранения кода/данных.
Если отталкиваться от полностью расслабленной модели памяти, то модель памяти x86 ведёт себя так, как будто в ней имеется ряд неявных барьеров памяти.
Но если ты хочешь формализма, то правильнее сказать, что в x86 некоторые виды барьеров в некоторых местах просто не нужны, а не неявные. Что имхо тождественно с практической точки зрения.
Здравствуйте, сипласплас, Вы писали:
С>Здравствуйте, WolfHound, Вы писали:
WH>>Здравствуйте, Константин Л., Вы писали:
С>[]
С>Ты хочешь сказать, что я могу не использовать Interlocked для изменения 32 битных чисел из разных трэдов и при этом _каждый_ трэд будет видеть их без задержек?
Это распростарённая ошибка касательно барьеров памяти. Барьеры памяти не имеют отношения к задержкам. Они не об этом.
С практической т.з. они скорее даже увеличивают задержки и время работы. Это как QоS против best-effort.
Если бы имелось какое-то средство, которое уменьшает задержки, то почему бы его не сделать неявным везде?!
Здравствуйте, GlebZ, Вы писали:
GZ>Здравствуйте, Кодт, Вы писали:
GZ>В этом смысле Cell интересно сделан.
Многие специалисты пророчат будущее именно для таких систем. Ну или по крайней мере, что Cell сильно повлияет на дальнейшее развитие...
Правда, модель Cell ещё на порядок сложнее в использовании сегодняшнего SMP/multicore? т.е. имеется одно центральное ядро "общего назначения", и ряд вспомогательных ядер, которые могут "перемножать матрицы". При этом общение этих ядер идёт не через shared memory, а через подобие DMA. Т.е. центральное ядро заливает во вспомогательное ядро данные, заливает программу, и командует действовать. Вспомогательное ядро выполняет обработку и сигнализирует центральное, что работа сделана. Далее через DMA данные выливаются из вспомогательного ядра.
Модель, определённо требующая специального и изначального дазайна программы именно под неё!
Здравствуйте, Cyberax, Вы писали:
C>Здравствуйте, eao197, Вы писали:
C>>>А почему тут происходят переключения контекстов? E>>Если нить ввода-вывода и нить обработки находятся на разных ядрах, то передача сообщений между ними оказывается дороже, чем при работе обоих нитей на одном ядре. По крайней мере, по моим впечатлениям. C>У меня впечатления обратные — передача данных через неблокирующуюся очередь (java.util.concurrent.ConcurrentNavigableMap, если кому интересно) у меня работает абсолютно с одинаковой скоростью на любом количестве процессоров (масштабируется почти линейно).
Здравствуйте, remark, Вы писали:
R>Не слышу! Говори громче! В другое ухо мне очень громко кричит CEO из Intel, о том какое крутое они сделали новое поколение процессоров, и о том, какие все программисты тупые, что ни как не могут научиться эффективно их использовать, хотя уже прошёл целый год, и они написали целых 2 white paper, о том, что надо программировать как-то по-новому.
Может выжидают , может ждуть пока кто то дельное предложит?
P.S. Практично посмотреть как монстры эти проблемы решают , как Эпик распаралеливает свои движки , как Havok свои и т.п.
Здравствуйте, RegisteredUser, Вы писали:
RU>Здравствуйте, remark, Вы писали:
R>>Скорее всего ты говоришь о какой-то очень ограниченной области применения, либо вообще о HPC.
RU>Нет, я говорю о языках общего назначения. Общеизвестный пример: на К написала большая часть kdb (говорят лидер рынка БД по производительности), набор трейдерских (то бишь зачастую очень real-time-овских) и других околофинансовых приложений (kx.com). Порылся на форумах JSoftware — нет, к сожалению текущая реализация J 601 никак не использует многоядерность, но принципиальных проблем с её использованием нет (ввиду implicit parallelism). RU>Просто эти языки и платформы предлагают иную (векторную сиречь _параллельную_) парадигму программирования (что не означает кстати, что они подходят лишь для перемножения матриц — обычные повседневные задачи тоже зачастую легко "векторизуются").
Я не спорю, что такие языки есть. За примерами далеко ходить не надо — OpenMP.
Единственная проблема, что такие языки ооооочень "ограниченные" в возможностях, которые они предоставляют программисту. Иначе они работать *не могут*! Они не могут просто так дать в руки программисту указатель и тому подобное.
И ещё вторая проблема, такие языки работают на 100% только при решении той самой задачи, которая была в голове у автора, когда он разрабатывал язык. В других случаях они работают процентов на 80-90. А если попытаешься добавить что-то, что плохо вписывается в модель, то можешь получить и 10%. А ведь никогда не знаешь, что может потребоваться завтра...
RU>Это был всего лишь мой пример существующего решения проблемы означенной в заглавии этой дискуссии. Продолжайте ломать копия о memory barrier-ы и прочие низкоуровневые детали реализации взгромождаемые традиционными постфортрановскими средствами разработки на плечи прикладного программиста
Во-первых, *никгода* не помешает хорошо разбираться во всех деталях используемой технологии. Хорошему Java/C# программисту не помешает разбираться, что такое указатель и стек. Не смотря на то, что язык полностью прячет это от него.
Во-вторых, а при чём тут прикладной программист. Если я делаю, допустим, кастомный движок для сервера, это не значит, что я потом пишу в прикладном коде: (1) увеличить баланс л/с. (2) выполнить барьер памяти. (3) проверить данные персоны.
Здравствуйте, minorlogic, Вы писали:
M>Здравствуйте, remark, Вы писали:
R>>Не слышу! Говори громче! В другое ухо мне очень громко кричит CEO из Intel, о том какое крутое они сделали новое поколение процессоров, и о том, какие все программисты тупые, что ни как не могут научиться эффективно их использовать, хотя уже прошёл целый год, и они написали целых 2 white paper, о том, что надо программировать как-то по-новому.
M>Может выжидают , может ждуть пока кто то дельное предложит?
Пускай молча ждут!
M>P.S. Практично посмотреть как монстры эти проблемы решают , как Эпик распаралеливает свои движки , как Havok свои и т.п.
У всех кастомные движки.
У Valve, например, смесь разделяемых структур и распараллеливания на основе задач.
На разделяемых структурах в частности сделана модель мира. Полностью lock-free. Причём разделена на 2 части: статическая (read-mostly) и динамическая. Видимо применяют что-то типа RCU.
Задачи сделаны достаточно традиционно. Прикладной программист просто выделяет некую задачу в выполняемый объект, который отдаётся шедулеру.
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, remark, Вы писали:
R>>Но основная беда даже не в этом.
R>>(опустим пока такие тривиальные вещи как сериализация на мьютексах)
R>>Передача кэш-линии занимает порядка 150-350 тактов. Даже без всяких атомарных операций и пр. R>>Т.е. скорость работы снижается до 100 (!) раз. Т.о. тривиальный producer-consumer может стать ботлнеком, если данные просто переходят из одного кэша в другой (без всяких atomic, мьютексов, евентов, вызовов я ядро для пробуждения consumer). R>>Плюс шина межпроцессорного/межядерного взаимодействия может стать боттлнеком, так что приложение просто не будет масштабироваться вообще при добавлении ядер, даже если потоков/работы достаточно, и нет сериализации на мьютексах, ядра не загружены и шина памяти не загружена.
К>Получается, что нужно сосредоточиться не только на стычках потоков вокруг общих данных (что всегда было предметом уважения), но и на стычках ядер вокруг линеек кеша.
К>Это означает, что К>- чем больше взаимодействие между потоками основано на пакетной обработке, тем лучше (впрочем, это и для одноядерных справедливо — в том плане, чтоб минимизировать переключения потоков) К>- для очередей, не предполагающих пакетную обработку — нужно разбрасывать элементы по разным линейкам К>Правильно?
К>На моей памяти это уже второй виток хардверно-специфических оптимизаций. Первый был, когда стали очень уважать попадание/промахивание в кэш своего ядра
Абсолютно правильно. Соперничество за линейки кэша даже более дорогое, чем промахивание мимо L2 (130 тактов).
В принципе, если на вскидку, попробовать оценить "стоимость" разделяемой структуры данных, то получается примерно так:
1. Кол-во атомарных операций (atomic rmw, InterlockedXXX). Это порядка 100 тактов. Плюс складывается со следующими пунктами.
2. Кол-во считываемых линеек кэша, которые модифицируются другими потоками. Перекачка строки из кэша в кэш порядка 150-350 тактов.
3. Кол-во линеек кэша, в которые производится запись. Не уверен вносит ли это дополнительное пенальти по сравнению с 2, но должно влиять на масштабируемость, т.к. все перекачки строк кэша вызваны тем, что в неё записал кто-то другой.
По моим представлениям, кол-во "потроганных" строк кэша — основной параметр влияющий на производительность.
Т.е. да, олучается, что если уж трогаешь вместе какие-то данные в разделяемой структуре, то лучше что бы они были в одной кэш-линии (пакетная обработка).
И да, если уж данные трогаются разными потоками несвязанно (нет пакетной обработки), то крайне противопоказано располагать их в одной кэш-линии. Это называется false sharing, когда данные как-бы не разделяются, но из-за того, что лежат в одной кэш-линии, получается, что разделяются.
В принципе multicore-aware аллокаторы специально выделяют каждый элемент выровненным по началу кэш-линии и занимают им всю линию. Правда кэш-линия сейчас в последних Intel 64/128 байт.
Категорически противопоказано выделять таблицы мьютектов подряд в памяти — каждый должен быть в своих 128 байтах — тут ещё примешивается т.н. cache line locking. Ну или если маленький объект содержит в себе мьютекс, то тоже самое.
Здравствуйте, AVM, Вы писали:
AVM>>>Вот блин и приплыли. В соответствии с Тезисом Чёрча—Тьюринга все можно посчитать с помошью машины Тьюринга. GZ>>Не понял??? В соответсвии с этим тезисом любая вычислимая функция может быть частично вычислена машиной Тьюринга. То есть с достаточном приближением. Вычислимость функции предполагает ее измеримость. То есть, ее можно вычислить данной машиной до определенной степени точности. Если у тебя величина бесконечность, то почему бы бесконечность не принять за некоторое значение обладающее соответвующими свойствами (есть же такое значение как null или NaN). AVM>В соответствии с тезисом "интуитивно вычислимая функция является частично вычислимой. Частично вычислимая может быть посчитана на машине Тьюринга". (Доказать или опровергнуть это не возможно, т.к. не совсем понятно что есть интуитивно вычислимая функция).
Совершенно верно. Поэтому это и называется тезисом, а не теоремой. Тезис Черча — про то, что наше интуитивное определение вычислимости сводимо к формальному определению алгоритма. Тезис был косвенно подтвержден строгими доказательствами эквивалентности различных определений алгоритма и вычислимости. AVM>Я не уверен, что пространство и время можно описать интуитивно вычислимой функцией.
Я не очень понимаю смысл выражения "описать пространство и время функцией". Пространство и время не описывают; они служат как бы холстом, на котором написана картина нашего мира. Физикам известно довольно много про пространство и время; в частности, однородность и анизотропность пространства хорошо подтверждены экспериментально, так же, как и равномерность времени.
Физики говорят о вычислимости применительно к алгоритмическому моделированию результатов эксперимента. Как в классической механике: дайте мне все координаты, массы и скорости, и я рассчитаю их значения в любой будущий или прошлый момент.
В квантовой механике оказалось, что прямо так координаты и скорости рассчитать нельзя; но это не из-за слабости нашей математики, а из-за устройства мира.
AVM>Следовательно я не уверен, что можно "обсчитать" пространство и время на машине Тьюринга.
Вот с этого и надо было начинать. Подвергать сомнению тезис Черча можно и нужно — на критике стоит весь научный метод познания.
Но пока что никаких симптомов его опровержения на горизонте не видно. Например, квантовые компьютеры никак не повлияли на трактовку понятия вычислимости. AVM>Это можно развивать дальше, но IMHO продолжать смысла нет.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, remark, Вы писали:
R>Занимаются они этим долго, но дозанимались они только до того, как быстро перемножать матрицы неимоверного размера. Да, там у них действительно есть автоматическое распараллеливание и т.д. R>Как мне это поможет при написании сетевого сервера?! Или развитого клиентского приложения?! R>Дай этому профи, который давно занимается распараллеливанием, такую задачу и он войдёт в ступор. Скорее всего он начнёт у тебя спрашивать "ну где тут этот самый массив на миллиард элементов, который надо распараллелить?", или "над чём тут делать преобразование Фурье?" R>А если задача что-нибудь посчитать, то есть средства типа OpenMP и иже с ним, их никто не игнорирует... если они всё-таки подходят.
Ну вот еще вопрос , а есть ли необходимость паралелить ВСЕ что можно ? Мы же слышали что тормозят только 15 — 20 процентов программы. Может как раз и стоит выделять критические куски и трансформировать их на стандартные алгоритмы ?
А обычные серверные приложения типа обработать N запросов... Тут можно банально запускать некое к-во процессов.
[]
R>Это распростарённая ошибка касательно барьеров памяти. Барьеры памяти не имеют отношения к задержкам. Они не об этом. R>С практической т.з. они скорее даже увеличивают задержки и время работы. Это как QоS против best-effort. R>Если бы имелось какое-то средство, которое уменьшает задержки, то почему бы его не сделать неявным везде?!
Что ты тут понимаешь под задержками? Я то, что изменение в одном трэде сразу видны в другом.
R>
Здравствуйте, GlebZ, Вы писали:
GZ>Если ты поставишь 1Тб и 80 ядерный процессор к себе на компьютер, то использовать позиционную сортировку ты все равно не сможешь. Сейчас мне пришлось заняться тиковыжимательством, и я пришел к выводу, что в нынешней архитектуре x86 нужно что-то менять. Проблема оказалась не в самом процессоре как таковом, он все успевает. Проблема оказалась в random доступе к памяти. Кэш проца в этом случае не спасает. Приходится сильно пере... алгоритмы чтобы запись была последовательна. Была еще проблема доступа к близким участкам памяти с нескольких процессоров. Но это достаточно легко решилось, хотя тоже через одно место.
+1
GZ>ЗЫ. Что касается Desktop, то для большинства бизнес-приложений, ресурсы процессора избыточен. Меня пока в этом не переубедили.
-1
... << RSDN@Home 1.2.0 alpha rev. 637>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, сипласплас, Вы писали:
С>Ты хочешь сказать, что я могу не использовать Interlocked для изменения 32 битных чисел из разных трэдов и при этом _каждый_ трэд будет видеть их без задержек?
For systems with multiple processors, hardware vendors need to ensure data coherency across all processors. Data coherency ensures that the data in all processor caches are updated when a single processor writes to the back up memory. This implies that there is a memory protocol that prevents one processor from overwriting data that another processor is using in its cache. Intel multiprocessor systems use the Modified — Exclusive — Shared — Invalid (MESI) protocol. This protocol ensures cache coherency of the internal cache lines of each processor.
When you first load the program data into a processor’s cache line, MESI requires the processor to mark the cache line with Exclusive (E) access, which gives that processor unlimited load/store access to the data on the cache line. However, if another processor requires access to the same data that already resides in another processor’s cache, MESI requires the processor to mark this line as Shared (S). For all subsequent stores to that cache line from any processor, the cache line is marked as Modified (M), which causes all processors with that cache line to Invalidate (I) the cache line and reload it from system memory.
E>Все это хорошо пока ты стороние библиотеки в свой проект не подключаешь. А как возьмешь к себе ACE, PCRE, Crypto++, да еще в виде DLL, так и запаришься в них нестандартные аллокаторы запихивать.
Так они же в исходниках идут, и у всех есть подключаемый конфигурационный h-заголовок, который инклюдится первым для любого cxx-файла. В этом конфигурационном заголовке прописал глобальные операторы new/delete и усё.
Здравствуйте, Константин Л., Вы писали:
КЛ>Здравствуйте, remark, Вы писали:
КЛ>[]
R>>Это распростарённая ошибка касательно барьеров памяти. Барьеры памяти не имеют отношения к задержкам. Они не об этом. R>>С практической т.з. они скорее даже увеличивают задержки и время работы. Это как QоS против best-effort. R>>Если бы имелось какое-то средство, которое уменьшает задержки, то почему бы его не сделать неявным везде?!
КЛ>Что ты тут понимаешь под задержками? Я то, что изменение в одном трэде сразу видны в другом.
Я тоже. Видимость сразу ничто не может обеспечить.
R>>
Здравствуйте, AVM, Вы писали:
AVM>Если серьезно, то на базе этого механизма (хранение генома в клетке) в перспективе можно строить очень хорошие хранилища информации: отношение емкость/размер — огромное, энергопотребление — низкое, защита информации от потерь — великолепная.
Если бы защита информации от потерь и вправду была бы великолепной, то никакой дивергенции (видообразования) вообще небыло бы.
AVM>Есть правда и куча минусов, основной — мы до сих пор не знаем как оно работает
А. Ну ну. Восхищение от природных решений чаще всего неосведомленностью и объясняется. Ну или ореолом некоей исключительности вокруг этих решений. Посмотрел бы я, что вы сказали бы о творениях инженера, который во-первых, полностью ограничен в выборе материала, во-вторых, не имеет возможности повторного использования предидущих решений и поэтому каждый день изобретает велосипед, в-третих, не может думать даже на пару ходов вперед (на самом деле, вообще не может думать) а решает все проблемы по мере возникновения, и так, как будто любое отдельно взятое решение — последнее. Ну а матушке-природе не то что все сойдет с рук — рукоплескания обеспечены.
... << RSDN@Home 1.2.0 alpha rev. 774>>
'You may call it "nonsense" if you like, but I'VE heard nonsense, compared with which that would be as sensible as a dictionary!' (c) Lewis Carroll
Здравствуйте, minorlogic, Вы писали:
M>Здравствуйте, remark, Вы писали:
R>>Занимаются они этим долго, но дозанимались они только до того, как быстро перемножать матрицы неимоверного размера. Да, там у них действительно есть автоматическое распараллеливание и т.д. R>>Как мне это поможет при написании сетевого сервера?! Или развитого клиентского приложения?! R>>Дай этому профи, который давно занимается распараллеливанием, такую задачу и он войдёт в ступор. Скорее всего он начнёт у тебя спрашивать "ну где тут этот самый массив на миллиард элементов, который надо распараллелить?", или "над чём тут делать преобразование Фурье?" R>>А если задача что-нибудь посчитать, то есть средства типа OpenMP и иже с ним, их никто не игнорирует... если они всё-таки подходят.
M>Ну вот еще вопрос , а есть ли необходимость паралелить ВСЕ что можно ? Мы же слышали что тормозят только 15 — 20 процентов программы. Может как раз и стоит выделять критические куски и трансформировать их на стандартные алгоритмы ?
M>А обычные серверные приложения типа обработать N запросов... Тут можно банально запускать некое к-во процессов.
Ну да, банально. Только надо обеспечить, что бы они могли принимать сообщения с одного активного сокета. Разделять read-mostly данные, балансировать между собой нагрузку и т.д.
