Кодёнок,
Кё>Нет, я хочу уничтожить в мире все калькуляторы Я не верю, что пошаговая инструкция для одного исполнителя в общем случае может быть переделана в инструкцию для нескольких исполнителей без полного анализа её смысла и переписывания.
А и не надо не верить. Достаточно заглянуть в учебники по вычислительной сложности.
Идея распараллеливания имеет смысл только если удаётся получить выигрыш. Если кроме усложнения алгоритма и нажитой головной боли мы не получим долгожданного ускорения, то грошь цена такой оптимизации. Думаю это понятно.
Теперь пример для охлаждения оптимизма: есть задача о Максимальном Независимом Множестве в графе. Независимое множество — это множество попарно несмежных вершин:
Задача формулируется просто: найти независимое множество максимальной мощности.
Вот жадный алгоритм для этой задачи:
Начинаем с пустого множества.
Пока текущий граф не пуст делаем следующее:
Добавляем вершину v с наименьшей степенью.
Удаляем все смежные с v.
Этот алгоритм невозможно параллелизовать в принципе. (это происходит потому, что каждое последовательное удаление вершины приводит к пересчёту всех степеней в графе, и пока пересчёт не будет выполнен, мы следующую вершину взять не сможем).
А заменить алгоритм можно не везде. Так что вывод мой будет таков: параллелится алгоритм — хорошо, нет — увы. Параллельная архитектура — хорошо, но это не будущее вычислений — она не универсальна
Здравствуйте, Cyberax, Вы писали: C>Такой язык есть уже много лет, называется Erlang. Минус его в том, что C>он чисто функциональный, а поэтому не всегда удобный.
1) Erlang не является чисто функциональным языком, побочные эффекты — его неотъемлемая черта.
2) То, что он местами функциональный (именно местами) является не минусом, а плюсом, так сделали специально, и "не всегда удобен" он совсем не поэтому.
3) Компилятор Erlang никогда не занимается автоматическим распараллеливанием. Ни при каких условиях. Параллелизм всегда явный.
4) Программист на Erlang должен думать о распаралеливании и синхронизации.
5) Таким образом, твой пост ошибочен практически везде — в каждом слове.
5) Мое мнение такое — не знаешь, не надо отвечать. Это же надо было облажаться в таком количестве мест. Не стыдно?
Кодёнок wrote: > Ествественно, это будет иметь смысл, если найдется способ генерировать > код программы так, чтобы он мог быть автоматически распараллелен на > очень большое число процессоров. Если развитие "Concurrent и Distributed > Programming" приведет к созданию компилятора, с которым не надо вообще > думать о разделении и синхронизаци — это будет идеальный случай; если > нет, то будет создан язык и возможно новая парадигма, где это будет > неотемлемой частью программирования, а не дополнительной головной болью.
Такой язык есть уже много лет, называется Erlang. Минус его в том, что
он чисто функциональный, а поэтому не всегда удобный.
Gaperton wrote: > C>Такой язык есть уже много лет, называется Erlang. Минус его в том, что > C>он чисто функциональный, а поэтому не всегда удобный. > 1) Erlang не является чисто функциональным языком, побочные эффекты — > его неотъемлемая черта.
Как раз наоборот — http://erlang.org/faq/x913.html#AEN930
> 3) Компилятор Erlang никогда не занимается автоматическим > распараллеливанием. Ни при каких условиях. Параллелизм всегда явный. > 4) Программист на Erlang должен думать о распаралеливании и синхронизации.
Не совсем так. В Erlang'е не нужно думать о низкоуровневой
синхронизации, так как нет разделяемых ресурсов. Метод общения объектов
— посылка [асинхронных] сообщений, так что внешние ресурсы элементарно
оборачиваются в отдельные потоки.
Текущая реализация Erlang'а не поддерживает автоматического
распараллеливания, однако оно возможно (что зафиксировано в стандартах
этого языка).
Здравствуйте, AndrewVK, Вы писали: AVK>Я уж думал мы договорились без аналогий. Обсуждать мозг я не хочу, здесь это оффтопик.
Точно. Он все равно с nutsом на курорте от японцев отбивается.
1.1.4 stable rev. 510
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
. Но почему ты думаешь, что интерес к этому направлению будет повышаться?
Мне представляется, что наиболее перспективное направление для дальнейшего развития железа — это не наращивание скорости одного калькулятора (сейчас уже два в одно ядро вставляют — одного мало ), который обслуживает всех, а использование десятка-другого простых процессоров (без хитрых конвееров, гипертредингов и сложных микрокодов). Например, наращивание мощности компа может производиться не апгрейдом процессора, а увеличением их количества.
Ествественно, это будет иметь смысл, если найдется способ генерировать код программы так, чтобы он мог быть автоматически распараллелен на очень большое число процессоров. Если развитие "Concurrent и Distributed Programming" приведет к созданию компилятора, с которым не надо вообще думать о разделении и синхронизаци — это будет идеальный случай; если нет, то будет создан язык и возможно новая парадигма, где это будет неотемлемой частью программирования, а не дополнительной головной болью.
Здравствуйте, Cyberax, Вы писали:
>> 1) Erlang не является чисто функциональным языком, побочные эффекты — >> его неотъемлемая черта. C>Как раз наоборот — http://erlang.org/faq/x913.html#AEN930
Как раз наоборот. Отсутствие разрушаещего присваивания не означает полного отсутствия побочных эффектов. Есть еще ввод-вывод во внешний мир, есть посылка сообщений другим процессам, есть process dictionary, есть всякие ets/dets, наконец.
>> 4) Программист на Erlang должен думать о распаралеливании и синхронизации. C>Не совсем так. В Erlang'е не нужно думать о низкоуровневой C>синхронизации, так как нет разделяемых ресурсов. Метод общения объектов C>- посылка [асинхронных] сообщений, так что внешние ресурсы элементарно C>оборачиваются в отдельные потоки.
Здравствуйте, mik1, Вы писали:
ANS>>Просто имена к файлам нужно прилинковывать в конце по факту копирования.
M>Это как? В CreateFile ничего подобного не помню.
Никак
M>А *nix мне, к сожалению, менее интересен, так как пользователи, увы — в Выньдоуз.
И в уних тоже никак. Хотя сама идея связана с особенностью работы унихов. Там при удалении файла через unlink (замечу, что это не удаление, а именно отцепление ссылки-имени) сам файл не удалится если на него будут ссылки. При том ссылкой будет считаться не только hard-link (другое имя), но и если файл открыт процессом. То есть, открытый файл можно "удалить", но открывший процесс этого не заметит. Физически файл будет удалён ОС после закрытия всех дескрипторов. И уже давно народ заприметил, что наряду с unlink полезно бы иметь и обратную опирацию, типа link. afaik, в текущих апи это невозможно, потому что нужна операция создания анонимного файла и операция прилинковки.
От себя могу добавить, что многим из тех алгоритмов, которые практически не параллелятся дикая скоростью вычислений и не нужна! Каждый из них можно и на одном процессоре выполнять, даже если этот процессор медленный.
Например, рисование интерфейса. Стандартные Windows-контролы и диалоги замечательно и очень быстро рисовались ещё когда у меня был машины Celeron-433 и Pentium-200MMX. А ведь это те же самые кнопочки, с которыми мы и сейчас работаем. Интерфейсы на Gecko и HtmLayout на Celeron-433 тоже отлично работали, а ведь там ещё есть что оптимизировать. Никаких больших потребностей в UI, с которыми бы они не справились, я ещё не встречал.
Много алгоритмов используют чтение и запись файлов, и ограничены быстродействием жестких дисков или флеш-памяти, которые ещё долго не смогут перегрузить тот же P200.
Здравствуйте, Кодёнок, Вы писали:
Кё>Если развитие "Concurrent и Distributed Programming" приведет к созданию компилятора, с которым не надо вообще думать о разделении и синхронизаци — это будет идеальный случай; если нет, то будет создан язык и возможно новая парадигма, где это будет неотемлемой частью программирования, а не дополнительной головной болью.
Во-первых, рассматривать "Concurrent и Distributed Programming" только в рамках одной программы, которая хитрым способом умным компилятором распараллеливается на независимые потоки исполнения -- это слишком зауженная интерпритация данного понятия. В более интересно создание и развитие технологий, которые позволят выходить не только за рамки одного компьютера и одного процесса, но и за рамки одного приложения. Т.е. развитие того, что сейчас делается с помощью CORBA или WebServices. Например, чтобы поисковая машина Google естественным образом становилось частью твоего приложения.
Во-вторых, от проблем синхронизации все равно никуда не уйдешь. Как бы тебе не помогали компиляторы и средства промежуточного слоя, если что-то работает параллельно, то синхронизироваться результаты работы должны в строго определенных местах. И если ты в выборе этих мест ошибаешься, то... сам понимаешь. А ошибиться очень просто.
SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Здравствуйте, Кодёнок, Вы писали:
Кё>Мне представляется, что наиболее перспективное направление для дальнейшего развития железа — это не наращивание скорости одного калькулятора (сейчас уже два в одно ядро вставляют — одного мало ), который обслуживает всех, а использование десятка-другого простых процессоров (без хитрых конвееров, гипертредингов и сложных микрокодов).
Ну... тут такая ситуация... Работать с одним процессором проще. Поэтому пока позволяют резервы, увеличивается мощность одного процессора. Как только возникает барьер --- вспоминают о том, что можно их поставить несколько
Фактически увеличение производительности можно добиться не только на уровне железа, но и на уровне софта
Зачем увеличивают производительность железа? В большинстве случаев, сделать более дешевым софт (более проста разработка, реализация, ...). Разрабатывать софт с поддержкой параллельной архитектуры сложнее, вполне может дешевле оказаться дешевле оптимизировать приложении под один процессор, чем поддерживать распараллеливание. Другое дело системы, в которых в ТЗ заложена параллельность
Брат Gaperton,
G>5) Таким образом, твой пост ошибочен практически везде — в каждом слове. G>5) Мое мнение такое — не знаешь, не надо отвечать. Это же надо было облажаться в таком количестве мест. Не стыдно?
Жостко. Ну ошибся человек, ну зачем же его так сразу втаптывать в ... Чуть-чуть терпимее.
Здравствуйте, Lazy Cjow Rhrr, Вы писали:
LCR>>>3. Вызовы типа prog1 | prog2 | prog3 ...
E>>А можно обосновать?
LCR>Напомню, что мы на юзерском уровне.
Юзеру вообще совершенно фиолетово, как они исполняются. Поэтому вести разговор на этом уровне мне не интересно. Поэтому предлагаю перейти на уровень программистов
LCR>Возможно prog1..n и параллелятся где-то в кишках, но сами программы должны выполняться последовательно, поскольку программа i+1 может требовать полностью вывод программы i.
Не полностью, а только то, что ей сейчас необходимо на текущем вводе.
LCR>Ну например, каждая из программ prog. выводит SUCCESS или FAILED, и это значение необходимо для следующей.
Первый grep работает совешенно ни с кем не синхронизируясь (хотя синхронизация на уровне ввода-вывода, когда второй grep не успевает вычитывать свой входной поток). Второй grep должен засыпать только, если на его входе больше ничего нет. Если же на входе есть выход из первого grep-а, то второй grep берет очередную строку и обрабатывает ее (работая параллельно с первым grep-ом). А уж вывод второго grep-а вообще никак не нужно синхронизировать с первым grep-ом.
LCR>Если ты по-прежнему неудовлетворён ответом, возьми наконец ant, make etc. Уж здесь железно, если таск2 зависит от таска1, то пока таск1 не отработает, таск2 не начинается. Это просто прибито гвоздями в спецификации.
Это уже другой пример.
SObjectizer: <микро>Агентно-ориентированное программирование на C++.
А почему вы спрашиваете wrote: > Как раз наоборот. Отсутствие разрушаещего присваивания не означает > полного отсутствия побочных эффектов.
Ну так в чисто функциональных языках тоже есть побочные эффекты. Без них
ничего нельзя сделать. Другое дело, что в Erlang'е они отделены в треды.
> C>Не совсем так. В Erlang'е не нужно думать о низкоуровневой > C>синхронизации, так как нет разделяемых ресурсов. Метод общения объектов > C>- посылка [асинхронных] сообщений, так что внешние ресурсы элементарно > C>оборачиваются в отдельные потоки. > Эту тему обсасывали здесь
Я в той теме тоже отметился
Здравствуйте, Cyberax, Вы писали:
C>А почему вы спрашиваете wrote: >> Как раз наоборот. Отсутствие разрушаещего присваивания не означает >> полного отсутствия побочных эффектов. C>Ну так в чисто функциональных языках тоже есть побочные эффекты. Без них C>ничего нельзя сделать. Другое дело, что в Erlang'е они отделены в треды.
В чисто функциональных языках нет побочных эффектов. Поэтому они и называются чисто функциональными.
Здравствуйте, GlebZ, Вы писали:
AVK>>А смысл? Все равно выборка токенов и их обработка в LL(1) производится последовательно. GZ>Не обязательно. Пока выделяется нода AST дерева, scanner ищет следующий токен.
Больше потеряешь на синхронизации.
AVK>>Она и так конвеерная, только каждый шаг в случае LL(1) зависит от предыдущего. GZ>В процах то же самое. Все зависит от предыдущего.
Здорово. Аргументы будут?
GZ> Только если иметь еще статистику(а статистика достаточно верная вещь), то можно построить и предсказательную логику.
Не путай теплое с мягким — предсказания нужны для спекулятивного выполнения, а не для разруливания зависимостей по данным.
AVK>>А мне кажется что это свойство природы такое. GZ>Нет. В природе все параллельно. Я могу идти, пить пиво, и думать одновременно.
Некорректная аналогия. Мы ведь о вычислениях говорим, а не о распитии спиртных напитков. Корректная аналогия — работа сознания. А вот оно почему то в норме не подвержено раздвоению, разтроению и т.д. Если же фоновое выполнение жизненно необходимо (дыхание, ходьба, етц) то природа пользуется "аппаратным сопроцессором" ака спинным мозгом. А вот так чтобы массовый параллелизм я в природе не припомню.
GZ> Вопрос в том, что сознательное мышление однопроцессорно.
Gaperton wrote: > C>Ну так в чисто функциональных языках тоже есть побочные эффекты. Без них > C>ничего нельзя сделать. Другое дело, что в Erlang'е они отделены в треды. > В чисто функциональных языках *нет *побочных эффектов. Поэтому они и > называются чисто функциональными.
Реальные программы _невозможны_ без побочных эффектов (типа ввода-вывода
данных). Поэтому для этого в ФЯ придумали монады: http://www.haskell.org/hawiki/UsingMonads
Здравствуйте, Cyberax, Вы писали:
C>Gaperton wrote: >> C>Ну так в чисто функциональных языках тоже есть побочные эффекты. Без них >> C>ничего нельзя сделать. Другое дело, что в Erlang'е они отделены в треды. >> В чисто функциональных языках *нет *побочных эффектов. Поэтому они и >> называются чисто функциональными. C>Реальные программы _невозможны_ без побочных эффектов (типа ввода-вывода C>данных). Поэтому для этого в ФЯ придумали монады: C>http://www.haskell.org/hawiki/UsingMonads
"Не совсем так" (С). А конкретнее, ты опять везде не прав.
На самом-то деле реальные программы на Хаскель, Миранда, и Clean, выполняющие ввод-вывод — свободны от побочных эффектов. А на языках ОКамл и Erlang — обладают побочным эффектом. Прикинь, фигня какая получается?
Пожтому для этого в ФЯ прекрасно обходились и обходятся без монад — они применяются только в Haskell. В Clean — уникальные типы, а в Miranda, которая была предшетвенником Хаскеля, не было ни монад, ни уникальных типов, ни побочных эффектов. А ввод-вывод при этом был, прикинь? А в Камле и Эрланге просто разрешены побочные эффекты, как в большинстве строгих языков — и для ввода-вывода не требуется ни монад, ни уникальных типов.
Можно спросить — зачем ты ЭТО пишешь? Должна же быть какая-то цель .
Здравствуйте, mik1, Вы писали:
M>У нас в ауле перед копированием проверяют свободное место на диске и общий объем файлов. И вообще не копируют, если они не влезут. Или Вы думаете, что во всех случаях корректнее скопировать часть файлов, чем ничего?
У Вас в ауле замирает жизнь и все стоят, затаив дыхание, когда Вы начинаете копировать файлы?
Здравствуйте, mik1, Вы писали:
M>Давным-давно слышал про поддержку sparse-файлов в NTFS. И ни разу не встречал приложений, использующих их. Подскажите, для расширения кругозора?
Не знаю на счет NTFS, но в юнихах "дырявые" файлы сплош и рядом. Замечу, что, afaik, в NTFS для этого нужны особые телодвижения, а в унихах "дырки" получаются "просто так".
Здравствуйте, Cyberax, Вы писали:
C>Такой язык есть уже много лет, называется Erlang. Минус его в том, что C>он чисто функциональный, а поэтому не всегда удобный.
Ну так я не имел ввиду чисто функциональный язык. Конечно, такое код легко параллелить, но он может работать только специально подготовленной для этого среде, которая бы для него выделяла и освобождала пямять и т.д.
Здравствуйте, Кодёнок, Вы писали:
Кё>...но он может работать только специально подготовленной для этого среде, которая бы для него выделяла и освобождала пямять и т.д.
Это ты про C# или Java?
Я к тому, что кого сейчас такие вещи пугают?
SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Здравствуйте, eao197, Вы писали:
Кё>>...но он может работать только специально подготовленной для этого среде, которая бы для него выделяла и освобождала память и т.д.
E>Это ты про C# или Java? E>Я к тому, что кого сейчас такие вещи пугают?
Я о том, что хоть чисто функциональный язык легко автоматически паралелится, на нём далеко не все задачи можно решить. Реализация стоящая за ним на самом деле модифицирует память, общается с устройствами и вообще производит кучу побочных эффектов... Так что не думаю, что Erlang годится на роль [единственного] языка общего назначения в той архитектуре, хотя может иметь очень широкое применение.
Кё>Ну так я не имел ввиду чисто функциональный язык. Конечно, такое код легко параллелить, но он может работать только специально подготовленной для этого среде, которая бы для него выделяла и освобождала пямять и т.д.
Проблема в том, что в императивных языках существует такая неприятная штука как внешние эффекты.
И фактически, описанием внешнего эффекта является тело конкретной функции или целой программы.
Получается, что в этом случае нужно построить такой суперкомпилятор, который бы формализировал внешние эффекты, находил те участки программы, которые могут быть распаралелены, и, соответственно, распаралеливал.
Как ты думаешь, насколько сложно и вообще возможно ли сделать такой компилятор?
Здравствуйте, Кодёнок, Вы писали:
Кё>Мне представляется, что наиболее перспективное направление для дальнейшего развития железа — это не наращивание скорости одного калькулятора (сейчас уже два в одно ядро вставляют — одного мало ), который обслуживает всех, а использование десятка-другого простых процессоров (без хитрых конвееров, гипертредингов и сложных микрокодов). Например, наращивание мощности компа может производиться не апгрейдом процессора, а увеличением их количества.
Чем больше процессоров, тем меньше алгоритмов способны их эффективно использовать. И никакой магический компилятор тут не поможет — он может распаралелить только если алгоритм поддается распаралеливанию.
... << RSDN@Home 1.2.0 alpha rev. 629 on Windows XP 5.1.2600.131072>>
Здравствуйте, Кодёнок, Вы писали:
Кё>Ествественно, это будет иметь смысл, если найдется способ генерировать код программы так, чтобы он мог быть автоматически распараллелен на очень большое число процессоров. Если развитие "Concurrent и Distributed Programming" приведет к созданию компилятора, с которым не надо вообще думать о разделении и синхронизаци — это будет идеальный случай; если нет, то будет создан язык и возможно новая парадигма, где это будет неотемлемой частью программирования, а не дополнительной головной болью.
Есть стандарт стандарт OpenMP. Пишешь в однопоточном императиве, тока стараясь так писать чтобы это можно было теоретически расспаралелить. Потом расставляешь специальные комментарии, где и какие данные меняются независимо. И все. После нескольких этапов — компиляции, профилирования, программа становится расспаралеленой в нужных местах.
Незнаю, как правда это на практике получается...
Насколько я понимаю, вы хотите примерно такого же, но только в компонентном программировании?
-- Главное про деструктор копирования не забыть --
Здравствуйте, AndrewVK, Вы писали:
Кё>>Мне представляется, что наиболее перспективное направление для дальнейшего развития железа — это не наращивание скорости одного калькулятора (сейчас уже два в одно ядро вставляют — одного мало ), который обслуживает всех, а использование десятка-другого простых процессоров (без хитрых конвееров, гипертредингов и сложных микрокодов). Например, наращивание мощности компа может производиться не апгрейдом процессора, а увеличением их количества.
AVK>Чем больше процессоров, тем меньше алгоритмов способны их эффективно использовать. И никакой магический компилятор тут не поможет — он может распаралелить только если алгоритм поддается распаралеливанию.
Может это проблема алгоритмов, и того, как мы привыкли думать об алгоритмах (один исполнитель).
Например, любую классическую сортировку распараллелить трудно, но если разрабатывать алгоритм специально для такой архитектуры, то может получиться например, когда несколько процессоров сортируют части, а затем один или два занимаются слиянием.
Здравствуйте, mishaa, Вы писали:
M>Есть стандарт стандарт OpenMP. Пишешь в однопоточном императиве, M>Незнаю, как правда это на практике получается... M>Насколько я понимаю, вы хотите примерно такого же, но только в компонентном программировании?
Нет, я хочу уничтожить в мире все калькуляторы Я не верю, что пошаговая инструкция для одного исполнителя в общем случае может быть переделана в инструкцию для нескольких исполнителей без полного анализа её смысла и переписывания.
Здравствуйте, Lazy Cjow Rhrr, Вы писали:
LCR>Брат Gaperton,
G>>5) Таким образом, твой пост ошибочен практически везде — в каждом слове. G>>5) Мое мнение такое — не знаешь, не надо отвечать. Это же надо было облажаться в таком количестве мест. Не стыдно?
LCR>Жостко. Ну ошибся человек, ну зачем же его так сразу втаптывать в ... Чуть-чуть терпимее.
Знаешь, я все понимаю, но настолько откровенная дезинформация — это уж слишком. Такое очень редко случается, к счастью. На моей памяти было всего несколько случаев за 3 года.
Здравствуйте, Gaperton, Вы писали:
G>4) Программист на Erlang должен думать о распаралеливании и синхронизации.
Имхо, это правильно. При разработке распределенных приложений лучше иметь инструмент, который позволяет программисту контролировать распараллеливание и синхронизацию, чем полагаться на то, что все как-то неявно будет работать так как надом.
SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Здравствуйте, Кодёнок, Вы писали:
Кё>Может это проблема алгоритмов, и того, как мы привыкли думать об алгоритмах (один исполнитель).
Наша привычка тут совершенно непричем. Возможность распараллеливания это объективная характеристика алгоритма. Если шаг Б зависит от результатов шага А, то никаким способом распараллелить их не удастся. Максимум, что тут можно сделать это выделить из алгоритма независимые части. Однако сам понимаешь, что таких независимых частей не бесконечно много и масштабируемость по количеству процессоров в общем случае невысока.
Кё>Например, любую классическую сортировку распараллелить трудно, но если разрабатывать алгоритм специально для такой архитектуры, то может получиться например, когда несколько процессоров сортируют части, а затем один или два занимаются слиянием.
Опять же далеко не факт что для некоторой задачи вобще существует такой алгоритм. И уж точно это не задача для компилятора.
Здравствуйте, Кодёнок, Вы писали:
Кё>Может это проблема алгоритмов, и того, как мы привыкли думать об алгоритмах (один исполнитель).
Кё>Например, любую классическую сортировку распараллелить трудно, но если разрабатывать алгоритм специально для такой архитектуры, то может получиться например, когда несколько процессоров сортируют части, а затем один или два занимаются слиянием.
Например, в третьем томе Кнута рассмотрен случай сортировки, когда доступно большое количество одновременно работающих компараторов. Если не ошибаюсь, алгоритм построения оптимального графа сравнений там нужно придумать в упражнении на 50 баллов.
По крайней мере, отсутствие решения этой задачи совершенно точно указывалось (у меня нет сабжа под рукой).
Конечно, сортировка слияниями легко поддается распараллеливанию. Вот только КПД у нее получится не слишком высокий.
1.1.4 stable rev. 510
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, AndrewVK, Вы писали:
AVK>Опять же далеко не факт что для некоторой задачи вобще существует такой алгоритм. И уж точно это не задача для компилятора.
Но и не факт, что для этой задачи обязательно будет нужна максимальная мощность всей системы. Может одного потока выполнения на медленном процессоре ей будет достаточно, если нас конечно продолжат кормить вещами вроде "мегакомпонентный WinForms на мегаобъектном GDI+ (оптимизируем попозже, а пока и так нормально)".
Здравствуйте, Sinclair, Вы писали:
S>Конечно, сортировка слияниями легко поддается распараллеливанию. Вот только КПД у нее получится не слишком высокий.
Однако, у наращивания скорости процессора есть физический предел, а у наращивания их количества — нет.
Вообще мне не нравится куда клонится беседа. Какие принципиально непараллелящиеся ресурсоемкие алгоритмы на вашем рабочем или домашнем компьютере работают дольше нескольких секунд?
Здравствуйте, Кодёнок, Вы писали:
Кё>Но и не факт, что для этой задачи обязательно будет нужна максимальная мощность всей системы. Может одного потока выполнения на медленном процессоре ей будет достаточно, если нас конечно продолжат кормить вещами вроде "мегакомпонентный WinForms на мегаобъектном GDI+ (оптимизируем попозже, а пока и так нормально)".
Все это здорово, но, как показывает практика, хорошо распаралеливающихся задач очень немного. И там где они есть как правило уже присутствуют различные аппаратные акселераторы вроде GPU.
Кодёнок,
Кё>Вообще мне не нравится куда клонится беседа. Какие принципиально непараллелящиеся ресурсоемкие алгоритмы на вашем рабочем или домашнем компьютере работают дольше нескольких секунд?
Ну если уж ты совсем опустился на юзерский уровень, вот тебе некоторые из них (может они принципиально и паралллелятся на каком-то низком уровне, но практически это последовательные):
1. Отображение html браузерами — пока не засосётся закрывающий тэг, браузер чаще всего вообще не может ничего показать.
2. Копирование n файлов из каталога А в каталог Б. Файлы копируются по-одному, и пока не будет скопирован i-й файл, не начинается копирование i+1-го.
3. Вызовы типа prog1 | prog2 | prog3 ...
4. Авторизация в системе. Пока не произойдёт рукопожатие (по строго последовательному протоколу), дальнейшие действия невозможны.
Здравствуйте, AndrewVK, Вы писали:
AVK>Здравствуйте, Кодёнок, Вы писали:
Кё>>Но и не факт, что для этой задачи обязательно будет нужна максимальная мощность всей системы. Может одного потока выполнения на медленном процессоре ей будет достаточно, если нас конечно продолжат кормить вещами вроде "мегакомпонентный WinForms на мегаобъектном GDI+ (оптимизируем попозже, а пока и так нормально)".
AVK>Все это здорово, но, как показывает практика, хорошо распаралеливающихся задач очень немного. И там где они есть как правило уже присутствуют различные аппаратные акселераторы вроде GPU.
Вы это про задачи общего использования или про специфические?
Из общих приходят в голову цивилизации, где в условиях мира между несколькими странами, все шаги каждой из них можно считать параллельно. Думаю, во многих других задачах все аналогично.
Еще в голову приходят архиваторы, где, например, разбив файл на две части (ну или, если файлов несколько, скармливая каждому потоку по одному из них) можно также легко распараллелить алгоритм (хотя и вероятно снижение степени компрессии).
Ну а о специфических алгоритмах Вам лучше прикладные математики и ВМКашники расскажут...
Здравствуйте, Lazy Cjow Rhrr, Вы писали:
Кё>>Вообще мне не нравится куда клонится беседа. Какие принципиально непараллелящиеся ресурсоемкие алгоритмы на вашем рабочем или домашнем компьютере работают дольше нескольких секунд?
LCR>2. Копирование n файлов из каталога А в каталог Б. Файлы копируются по-одному, и пока не будет скопирован i-й файл, не начинается копирование i+1-го.
А кто мешает копировать их параллельно? Или Вы думаете, что гарантированно выжмете всю пропускную способность файловой системы и при копировании одиночных файлов?
LCR>3. Вызовы типа prog1 | prog2 | prog3 ...
Только если между программами есть зависимости (явные — по данным, или неявные — по косвенным эффектам выполнения).
mik1,
LCR>>2. Копирование n файлов из каталога А в каталог Б. Файлы копируются по-одному, и пока не будет скопирован i-й файл, не начинается копирование i+1-го.
M>А кто мешает копировать их параллельно? Или Вы думаете, что гарантированно выжмете всю пропускную способность файловой системы и при копировании одиночных файлов?
Да. Если бы пропускная способность файловой системы (а конкретно шины винчестера) была выше, то и копирование одного файла было бы быстрее А при копировании нескольких файлов одновременно будет наверное ещё хуже, потому что дёргание головки винчестеров тоже небесплатное.
Я говорю про копирование с одного каталога в другой на том же самом винчестере.
LCR>>3. Вызовы типа prog1 | prog2 | prog3 ...
M>Только если между программами есть зависимости (явные — по данным, или неявные — по косвенным эффектам выполнения).
Да, если каждая из программ будет в конце своей работы выводить неизвестное априори сообщение, то такая зависимость налицо.
Здравствуйте, mik1, Вы писали:
AVK>>Все это здорово, но, как показывает практика, хорошо распаралеливающихся задач очень немного. И там где они есть как правило уже присутствуют различные аппаратные акселераторы вроде GPU.
M>Вы это про задачи общего использования или про специфические?
Про первое.
M>Из общих приходят в голову цивилизации, где в условиях мира между несколькими странами, все шаги каждой из них можно считать параллельно. Думаю, во многих других задачах все аналогично.
Собственно лично я знаю всего несколько хорошо распараллеливающихся задач — моделирование, 3D, обработка сигнальных потоков. Первое вряд ли задача для десктопов, а для остального существуют аппаратные акселераторы и векторные сопроцессоры.
Евгений.
LCR>>3. Вызовы типа prog1 | prog2 | prog3 ...
E>А можно обосновать?
Напомню, что мы на юзерском уровне. Возможно prog1..n и параллелятся где-то в кишках, но сами программы должны выполняться последовательно, поскольку программа i+1 может требовать полностью вывод программы i.
Ну например, каждая из программ prog. выводит SUCCESS или FAILED, и это значение необходимо для следующей.
Если ты по-прежнему неудовлетворён ответом, возьми наконец ant, make etc. Уж здесь железно, если таск2 зависит от таска1, то пока таск1 не отработает, таск2 не начинается. Это просто прибито гвоздями в спецификации.
Здравствуйте, Lazy Cjow Rhrr, Вы писали:
LCR>1. Отображение html браузерами — пока не засосётся закрывающий тэг, браузер чаще всего вообще не может ничего показать.
Это проблема layout engine. Например, у Gecko родительский блок может "расти", удлиняться по мере того, как загружаются новые дочерние элементы. Хотя я не понимаю как это относится к распараллеливанию.
В этом случа можно как минимум распараллелить
1. Чтение из файла и парсинг.
2. Изменение DOM, пересчёт стилей.
3. Форматирование.
4. Посылка на экран.
Но это чисто фантазия, надо спросить у того, у кого есть опыт, например у c-smile.
LCR>2. Копирование n файлов из каталога А в каталог Б. Файлы копируются по-одному, и пока не будет скопирован i-й файл, не начинается копирование i+1-го.
Нересурсоемкий. Если это не скачка с FTP, где бывает целесообразно пускать несколько файлов одновременно, то всё упирается в скорость файловой системы, поэтому параллелить не нужно. А если это даст выигрыш, то каждый процессор может копировать по файлу.
Дополнительные процессоры могут заниматься распаковкой и расшифровкой файлов, если нужно.
LCR>3. Вызовы типа prog1 | prog2 | prog3 ...
-1, каждая программа может выполняться на отдельном процессоре (как минимум).
LCR>4. Авторизация в системе.
Нересурсоемкий. Те процессы, которые уже работают, будут работать как всегда. Те что еще не запущены, нас не интересуют Если на каком-нибудь сервере с громадным числом пользователей это важно, то некоторые сессии и оболочки могут быть предзагружены, опять же в разные процессоры, и по мере логинов (опять же каждый логин на своём процессоре) будут раздаваться.
LCR>Ещё продолжать?
Да, пожалуйста.
Я думаю, надо не гадать, а подумать. Если такие задачи есть, то в процессе их выполнение вы не работаете на компьютере, а ждете их выполнения. Пример: компиляция, архивания. Но в общем, на рабочей станции таких сложных вычислений нет, иначе смысл многозадачности сильно уменьшается (во время их выполнения вы не можете использовать компьютер на полную мощность).
Здравствуйте, Lazy Cjow Rhrr, Вы писали:
LCR>Да, если каждая из программ будет в конце своей работы выводить неизвестное априори сообщение, то такая зависимость налицо.
1. Если программы передают данные во время всего своего времени работы (канал), то они выполняются параллельно.
2. Если они передают данные только как результат, то вся работа алгоритма сводится к запуску нескольких процессов. При этом запуск 3 процессов одним быстрым процессором, или одним медленных и запуск трех процессов одновременно разными процессорами ничем особо не отличаются, т.к. всё равно обычно упираются в скорость чтения с диска. В крайнем слуае, если инициализация тяжелая, то распараллеливание не проиграет.
Исходный вопрос был о ситуациях, когда параллелить НУЖНО (имеет смысл).
Здравствуйте, Кодёнок, Вы писали:
Кё>Однако, у наращивания скорости процессора есть физический предел, а у наращивания их количества — нет.
Речь идет о том, что просто "разрабатывать алгоритм специально для такой архитектуры" недостаточно для получения реального выхлопа от роста количества процессоров.
Видишь ли, насколько мне известно, данной тематикой занимаются целые институты — всякие там раскрашенные сети петри и так далее — но результатов я в общем-то не знаю. Еще раз намекну про то, что решения для оптимальной загрузки процессоров сортировкой не существует. А очевидные решения быстро выходят на насыщение, и дальнейшее увеличение количества процессоров не приводит к росту производительности! Кё>Вообще мне не нравится куда клонится беседа. Какие принципиально непараллелящиеся ресурсоемкие алгоритмы на вашем рабочем или домашнем компьютере работают дольше нескольких секунд?
Экий ты быстрый. Вопрос про принципиальную параллелящесть сам по себе требует нехилого исследования для каждого конкретного случая. Что-то из области "перечислите все еще неоткрытые элементарные частицы. Объясните причины, препятствующие их открытию в настоящий момент".
Я всего лишь хотел несколько охладить оптимизм по поводу распараллеливания вычислений.
1.1.4 stable rev. 510
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Да, тормоза 1-го и 2-го примеров связаны с тормозами на транспортном уровне. Я их привёл потому, что они последовательные с точки зрения пользователя (мы же здесь думаем про обычный, а не теоретически наилучший случай, не так ли?).
LCR>>3. Вызовы типа prog1 | prog2 | prog3 ... Кё>-1, каждая программа может выполняться на отдельном процессоре (как минимум).
Там я ответил eao где привёл ситуацию. Там пока будет выполняться prog1, остальные будут смиренно дожидаться своей очереди. Да. Зато каждая задача будет иметь свой собственный процессор, можно только порадоваться за задачи Но каждая задача — атом с точки зрения этой цепочки.
LCR>>4. Авторизация в системе. Кё>Нересурсоемкий. Те процессы, которые уже работают, будут работать как всегда. Те что еще не запущены, нас не интересуют Если на каком-нибудь сервере с громадным числом пользователей это важно, то некоторые сессии и оболочки могут быть предзагружены, опять же в разные процессоры, и по мере логинов (опять же каждый логин на своём процессоре) будут раздаваться.
Да нет, авторизация может выполняться очень долго. И это уже не связано с транспортом, а связано с вычислением хэшей. Хэши вычисляются последовательно, результат вычисления одного алгоритма хэширования является входом другого. То есть вычисление хэша — это атомарный вычислительный процесс.
Кё>Я думаю, надо не гадать, а подумать. Если такие задачи есть, то в процессе их выполнение вы не работаете на компьютере, а ждете их выполнения. Пример: компиляция, архивания. Но в общем, на рабочей станции таких сложных вычислений нет, иначе смысл многозадачности сильно уменьшается (во время их выполнения вы не можете использовать компьютер на полную мощность).
Именно!!! большинство тормозных десктопных задач софсем не связано с нагрузкой на процессор (а например, на сетку или диск). Здесь мы с тобой (да и не только) солидарны.
Поэтому любая десктопная непаралелящаяся задача будет "нересурсоёмкой", а любая тяжёлая непараллелящиеся задача — "специфической".
Вот я и гадаю, что бы ты хотел на "приведите мне десктопные ресурсоёмкие задачи"?
Здравствуйте, Lazy Cjow Rhrr, Вы писали:
LCR>mik1,
LCR>>>2. Копирование n файлов из каталога А в каталог Б. Файлы копируются по-одному, и пока не будет скопирован i-й файл, не начинается копирование i+1-го.
M>>А кто мешает копировать их параллельно? Или Вы думаете, что гарантированно выжмете всю пропускную способность файловой системы и при копировании одиночных файлов?
LCR>Да. Если бы пропускная способность файловой системы (а конкретно шины винчестера) была выше, то и копирование одного файла было бы быстрее А при копировании нескольких файлов одновременно будет наверное ещё хуже, потому что дёргание головки винчестеров тоже небесплатное.
LCR>Я говорю про копирование с одного каталога в другой на том же самом винчестере.
Ай-яй-яй. Какое правильное условие добавлено А мне как-то чаще приходится с CD/DVD или FTP копировать, чем между папками на одном винчестере. А винчестер может быть и не один (мы же помним один из советов Microsoft о том, что swap-файл, если есть возможность, надо размещать двумя частями на двух физических дисках. Чувствую, что они то параллельную запись тут реализовали).
LCR>>>3. Вызовы типа prog1 | prog2 | prog3 ...
M>>Только если между программами есть зависимости (явные — по данным, или неявные — по косвенным эффектам выполнения).
LCR>Да, если каждая из программ будет в конце своей работы выводить неизвестное априори сообщение, то такая зависимость налицо.
Команда "|" не подразумевает этого. Опять же в первоначальном сообщении об этом сказано не было
Здравствуйте, AndrewVK, Вы писали:
AVK>Здравствуйте, Кодёнок, Вы писали:
Кё>>Но и не факт, что для этой задачи обязательно будет нужна максимальная мощность всей системы. Может одного потока выполнения на медленном процессоре ей будет достаточно, если нас конечно продолжат кормить вещами вроде "мегакомпонентный WinForms на мегаобъектном GDI+ (оптимизируем попозже, а пока и так нормально)".
AVK>Все это здорово, но, как показывает практика, хорошо распаралеливающихся задач очень немного. И там где они есть как правило уже присутствуют различные аппаратные акселераторы вроде GPU.
Забавная вещь. Работаю в банке. Казалось, что 99% работы составит либо рисование формочек, либо написание sql-запросов. Но вот частенько попадабтся задачи, которые иногда и не мешает распараллелить.
Например. Есть список ФИО сотрудников банка + кодов их подразделений. Есть списки пользователей различных информационных подсистем. Нужно сопоставить каждому пользователю из этих списков его код подразделения. Задача параллелится великолепно. А последовательно на 3 ГГц отрабатывает минут за 40...
Есть и другие задачи. Самый их главный критерий — их нельзя эффективно описать на SQL
А вот и с SQL пришло в голову. Длительная инициализация программы, состоящая в чтении данных из СУБД. Данные есть как зависящие от предыдущих считанных, так и не зависящие. Известно, что сервер недогружен. Почему бы не пустить инициализацию независимых блоков данных параллельно? Пользователю бы пришлось ждать меньше. Надеюсь, что задача для многих каждодневная и актуальная.
mik1,
M>Ай-яй-яй. Какое правильное условие добавлено А мне как-то чаще приходится с CD/DVD или FTP копировать, чем между папками на одном винчестере.
И тормоза сохраняются...
M> А винчестер может быть и не один (мы же помним один из советов Microsoft о том, что swap-файл, если есть возможность, надо размещать двумя частями на двух физических дисках. Чувствую, что они то параллельную запись тут реализовали).
Ну это уже детали, понимаешь. Опять же, для всех (даже для меня ) совершенно очевидно, что алгоритм "присваивание массива массиву" можно распараллелить.
M>Команда "|" не подразумевает этого. Опять же в первоначальном сообщении об этом сказано не было
Да, конечно.
Да, я потом вспомнил про ленивые потоки. Да вообще, я бы хотел от Кодёнка получить конкретизацию вопроса, какие такие непараллелящиеся задачи ему нужно, прежде чем продолжать искать. А то мои примеры сумбурные какие-то.
Здравствуйте, mik1, Вы писали:
M>Например. Есть список ФИО сотрудников банка + кодов их подразделений. Есть списки пользователей различных информационных подсистем. Нужно сопоставить каждому пользователю из этих списков его код подразделения. Задача параллелится великолепно. А последовательно на 3 ГГц отрабатывает минут за 40...
А ты уверен что упирается все в процессор, а не в диск?
M>А вот и с SQL пришло в голову. Длительная инициализация программы, состоящая в чтении данных из СУБД. Данные есть как зависящие от предыдущих считанных, так и не зависящие. Известно, что сервер недогружен. Почему бы не пустить инициализацию независимых блоков данных параллельно? Пользователю бы пришлось ждать меньше. Надеюсь, что задача для многих каждодневная и актуальная.
Это все штучные процессоры. Предлагается же массовый параллелизм.
Здравствуйте, Кодёнок, Вы писали:
Кё>Я думаю, надо не гадать, а подумать. Если такие задачи есть, то в процессе их выполнение вы не работаете на компьютере, а ждете их выполнения. Пример: компиляция, архивания.
Хороший пример. Расскажи как распараллелить скажем парсинг LL(1) грамматики.
Здравствуйте, AndrewVK, Вы писали:
AVK>Здравствуйте, mik1, Вы писали:
M>>Например. Есть список ФИО сотрудников банка + кодов их подразделений. Есть списки пользователей различных информационных подсистем. Нужно сопоставить каждому пользователю из этих списков его код подразделения. Задача параллелится великолепно. А последовательно на 3 ГГц отрабатывает минут за 40...
AVK>А ты уверен что упирается все в процессор, а не в диск?
Уверен
Когда все это время загрузка CPU висит на 100% — то уверен. А самих данных — меньше 3 мегабайт.
Хотя есть и моя лень — все читается прямо из Excel.Application, что не добавляет скорости (вызовы COM EXE-сервера).
Но все равно — больная часть данных заведена в формате не "ИВАНОВ ИВАН ИВАНЫЧ", а "ИВАНОВ И.И." или "ИВАНОВ ИВАН" или "ИВАНОВ И." и машине приходится тратить время на двоичный поиск элемента, который будет вероятно сопадать с этой строкой.
M>>А вот и с SQL пришло в голову. Длительная инициализация программы, состоящая в чтении данных из СУБД. Данные есть как зависящие от предыдущих считанных, так и не зависящие. Известно, что сервер недогружен. Почему бы не пустить инициализацию независимых блоков данных параллельно? Пользователю бы пришлось ждать меньше. Надеюсь, что задача для многих каждодневная и актуальная.
AVK>Это все штучные процессоры. Предлагается же массовый параллелизм.
А что касается массового параллелизма, про который Вы говорили в первом Вашем посте в теме, то как вы собираетесь скрестить ДЕСКТОПНЫЕ задачи (по умолчанию не требовательные к ресурсам) и много процессоров (грубо говоря, кластер)? Какому пользователю придет в голову купить себе домой кластер?
Ну а если таки придет ему это в голову — то вспомним задачи обработки данных, о которыч я уже говорил — перегонка видео в другой формат, архивация файлов и т.д. — все они могут быть крупнозернисто распараллелены.
Здравствуйте, Sinclair, Вы писали:
S>Здравствуйте, Кодёнок, Вы писали:
Кё>>Может это проблема алгоритмов, и того, как мы привыкли думать об алгоритмах (один исполнитель).
Кё>>Например, любую классическую сортировку распараллелить трудно, но если разрабатывать алгоритм специально для такой архитектуры, то может получиться например, когда несколько процессоров сортируют части, а затем один или два занимаются слиянием. S>Например, в третьем томе Кнута рассмотрен случай сортировки, когда доступно большое количество одновременно работающих компараторов. Если не ошибаюсь, алгоритм построения оптимального графа сравнений там нужно придумать в упражнении на 50 баллов. S>По крайней мере, отсутствие решения этой задачи совершенно точно указывалось (у меня нет сабжа под рукой). S>Конечно, сортировка слияниями легко поддается распараллеливанию. Вот только КПД у нее получится не слишком высокий.
Да практически каждый рекурсивный алгоритм можно легко распараллелить. Я не понял чего тут страшного в сортировке.
Возьмем тот же quick sort:
template <class SType>
void __fastcall QuickSort(SType *item, int left, int right)
{
int i, j;
SType center;
SType x;
i = left;
j = right;
center = item[(left + right) 2];
while(i <= j)
{
while (item[i] < center && i < right)
i++;
while (item[j] > center && j > left)
j--;
if (i<=j){
x = item[i];
item[i] = item[j];
item[j] = x;
i++;
j--;
}
}
if(left < j)
QuickSort(item, left, j);
// а вот эту часть поставить в очередь задач для параллельного выполнения
if(right > i)
QuickSort(item, i, right);
}
Здравствуйте, Lazy Cjow Rhrr, Вы писали:
LCR>Короче, чтобы воспользоваться параллельными вычислениями, нужно заменить алгоритм. (Например, взять для этой задачи алгоритм Luby: http://www.dcg.ethz.ch/members/pascal/refs/mis_1986_luby.pdf).
Абсолютно правильно. Но штука в следующем, последовательные алгоритмы на параллельном процессоре можно выполнить. А вот парралельные алгоритмы на простом проце, уже трудно.
И вообще, с графами есть группа алгоритмов связанная с некоторым количеством курсоров, которые бегают по нему, и помечають. В условиях одного процессора они, мягко говоря, не очень эффективны.
LCR>А заменить алгоритм можно не везде.
Это еще почему?
Здравствуйте, GlebZ, Вы писали:
GZ>Да практически каждый рекурсивный алгоритм можно легко распараллелить. Я не понял чего тут страшного в сортировке. GZ>Возьмем тот же quick sort: GZ>
GZ>template <class SType>
GZ>void __fastcall QuickSort(SType *item, int left, int right)
GZ>{
GZ> //поскипано
GZ> if(left < j)
GZ> QuickSort(item, left, j);
GZ> // а вот эту часть поставить в очередь задач для параллельного выполнения
GZ> if(right > i)
GZ> QuickSort(item, i, right);
GZ>}
GZ>
Ну возьмем хотя бы затраты на пересылку этой части массива на другой компьютер... по 100-мегабитной сетке... в которой, кроме нас, есть еще кто-то... скорее всего, этот алгоритм будет эффективно параллелиться только на многопроцессорнике.
Здравствуйте, AndrewVK, Вы писали:
AVK>Хороший пример. Расскажи как распараллелить скажем парсинг LL(1) грамматики.
Тут я уже не понял. Ты о чем, о задачах, или об алгоритмах? В случае здесь обсуждавшегося Эрли, то насколько я понял, то его параллелить можно. В принципе, при достаточной степени маразма можно и его распараллелить, поскольку можно заглядывать на один токен далее чтобы уменьшить влияние откатов.
В принципе, обработка очереди символов не параллельная задача. Но вот что за ним следует(типа семантика и прагматика) то ее спокойно можно параллельно делать.
Здравствуйте, mik1, Вы писали:
M>Ну возьмем хотя бы затраты на пересылку этой части массива на другой компьютер... по 100-мегабитной сетке... в которой, кроме нас, есть еще кто-то... скорее всего, этот алгоритм будет эффективно параллелиться только на многопроцессорнике.
Опаньки. А кто говорил про сетку? Я чего-то пропустил? Перечитай root. Здесь даже не говорили о разделении памяти для процессоров.
Здравствуйте, mik1, Вы писали:
M>>>Например. Есть список ФИО сотрудников банка + кодов их подразделений. Есть списки пользователей различных информационных подсистем. Нужно сопоставить каждому пользователю из этих списков его код подразделения. Задача параллелится великолепно. А последовательно на 3 ГГц отрабатывает минут за 40...
AVK>>А ты уверен что упирается все в процессор, а не в диск?
M>Уверен
Тогда очень странно. Сколько ж там этих пользователей, что банальный поиск по хеш-таблице 40 минут занимает?.
M>Когда все это время загрузка CPU висит на 100% — то уверен. А самих данных — меньше 3 мегабайт.
Ну тогда это явно проблемы в алгоритмах.
M>Хотя есть и моя лень — все читается прямо из Excel.Application, что не добавляет скорости (вызовы COM EXE-сервера).
А, ну так с этого и надо начинать.
M>Но все равно — больная часть данных заведена в формате не "ИВАНОВ ИВАН ИВАНЫЧ", а "ИВАНОВ И.И." или "ИВАНОВ ИВАН" или "ИВАНОВ И." и машине приходится тратить время на двоичный поиск элемента, который будет вероятно сопадать с этой строкой.
Это все для современных процессоров ничтожные копейки. Выгружай из екселя в xml, а внутри программы в спец. структуру, используй эффективные алгоритмы и твои 40 минут превратятся в пару секунд.
AVK>>Это все штучные процессоры. Предлагается же массовый параллелизм.
M>А что касается массового параллелизма, про который Вы говорили в первом Вашем посте в теме,
Не я, Коденок.
M> то как вы собираетесь скрестить ДЕСКТОПНЫЕ задачи (по умолчанию не требовательные к ресурсам) и много процессоров (грубо говоря, кластер)? Какому пользователю придет в голову купить себе домой кластер?
Здравствуйте, GlebZ, Вы писали:
GZ>Опаньки. А кто говорил про сетку? Я чего-то пропустил? Перечитай root. Здесь даже не говорили о разделении памяти для процессоров.
А вообще-то в другой ветке мы с Mamut-ом заговорили об одном, а здесь Коденок все свел к железу и одному компьютеру (пусть даже и многопроцессорному).
Тема из Concurent и Distributed Programming ушла в Concurent и Parallel Computing, имхо.
SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Здравствуйте, GlebZ, Вы писали:
AVK>>Хороший пример. Расскажи как распараллелить скажем парсинг LL(1) грамматики. GZ>Тут я уже не понял. Ты о чем, о задачах, или об алгоритмах? В случае здесь обсуждавшегося Эрли, то насколько я понял, то его параллелить можно.
Можно только в случае, если грамматика содержит альтернативы. А если это LL(1) грамматика, то параллелить там нечего.
Вобще говоря, "Concurrent" — это когда мы запускаем несколько задач (возможно, на одном процессоре от избытка мощности ).
А когда распараллеливают программы, это называется "Parallel Programming".
Здравствуйте, AndrewVK, Вы писали:
AVK>Можно только в случае, если грамматика содержит альтернативы. А если это LL(1) грамматика, то параллелить там нечего.
Да можно параллелить. Хоть в конечном автомате. Один процесс сканирует токены, второй их обрабатывает. Можно и еще хуже. Сделать конвейерную обработку. Процы работают же с предсказательной логикой, а вот программные алгоритмы редко. Вобщем, порезвиться можно и на такой шняге.
А вообще, должен сказать что испокон веков математика была однопроцессорной. Начиная от Архимеда с Эвклидами. И сейчас не сильно поменялось. Большинство алгоритмов стараются описать пошагово. Параллельные описывались только когда не было нормального однопроцессорного алгоритма. Поэтому первая причина однопроцессорности именно в недоразвитости математики и алгоритмов.
Здравствуйте, GlebZ, Вы писали:
AVK>>Можно только в случае, если грамматика содержит альтернативы. А если это LL(1) грамматика, то параллелить там нечего. GZ>Да можно параллелить.
Что?
GZ> Хоть в конечном автомате. Один процесс сканирует токены, второй их обрабатывает.
А смысл? Все равно выборка токенов и их обработка в LL(1) производится последовательно.
GZ> Можно и еще хуже. Сделать конвейерную обработку.
Она и так конвеерная, только каждый шаг в случае LL(1) зависит от предыдущего.
GZ>А вообще, должен сказать что испокон веков математика была однопроцессорной. Начиная от Архимеда с Эвклидами. И сейчас не сильно поменялось. Большинство алгоритмов стараются описать пошагово. Параллельные описывались только когда не было нормального однопроцессорного алгоритма. Поэтому первая причина однопроцессорности именно в недоразвитости математики и алгоритмов.
Здравствуйте, AndrewVK, Вы писали:
GZ>> Хоть в конечном автомате. Один процесс сканирует токены, второй их обрабатывает. AVK>А смысл? Все равно выборка токенов и их обработка в LL(1) производится последовательно.
Не обязательно. Пока выделяется нода AST дерева, scanner ищет следующий токен.
GZ>> Можно и еще хуже. Сделать конвейерную обработку. AVK>Она и так конвеерная, только каждый шаг в случае LL(1) зависит от предыдущего.
В процах то же самое. Все зависит от предыдущего. Только если иметь еще статистику(а статистика достаточно верная вещь), то можно построить и предсказательную логику.
GZ>>А вообще, должен сказать что испокон веков математика была однопроцессорной. Начиная от Архимеда с Эвклидами. И сейчас не сильно поменялось. Большинство алгоритмов стараются описать пошагово. Параллельные описывались только когда не было нормального однопроцессорного алгоритма. Поэтому первая причина однопроцессорности именно в недоразвитости математики и алгоритмов. AVK>А мне кажется что это свойство природы такое.
Нет. В природе все параллельно. Я могу идти, пить пиво, и думать одновременно. Вопрос в том, что сознательное мышление однопроцессорно. Над двумя вещами думать одновременно мы не умеем. В отличие от механизмов которые мы умеем делать.
Здравствуйте, Cyberax, Вы писали:
C>Gaperton wrote: >> C>Такой язык есть уже много лет, называется Erlang. Минус его в том, что >> C>он чисто функциональный, а поэтому не всегда удобный. >> 1) Erlang не является чисто функциональным языком, побочные эффекты — >> его неотъемлемая черта. C>Как раз наоборот — http://erlang.org/faq/x913.html#AEN930
Почитай мануал по Эрлангу, и задайся вопросом, не обладает ли случайно оператор посылки сообщения "!" побочным эффектом. Как связаны понятия "побочный эффект" и "чисто функциональный" я думаю объяснять не надо, мы же тут все специалисты? Но на всякий случай: об этом сказано в факе comp.lang.functional или в википедии.
Также обрати внимание на такие штуки, как "словарь" процесса, таблицы dets, организацию ввода-вывода, и mnesia. Да, в факе информации не так много, к сожалению для этого придется читать мануал.
Хотя специалиста уже тот факт, что язык строгий, навел бы на мысли о том, что он скорее всего не является чисто функциональным. А этот факт нельзя пропустить даже при поверхностном знакомстве с языком.
>> 3) Компилятор Erlang никогда не занимается автоматическим >> распараллеливанием. Ни при каких условиях. Параллелизм всегда явный. >> 4) Программист на Erlang должен думать о распаралеливании и синхронизации. C>Не совсем так. В Erlang'е не нужно думать о низкоуровневой C>синхронизации, так как нет разделяемых ресурсов. Метод общения объектов C>- посылка [асинхронных] сообщений, так что внешние ресурсы элементарно C>оборачиваются в отдельные потоки.
Совсем так. Хотел бы я посмотреть, как ты скоординированно поменяешь два "внешних" ресурса без синхронизации — это случай распределенной транзакции, возникающий сплошь и рядом.
Кстати, объектов в Эрланге нет, и потоков тоже. Там есть процессы. А асинхронными сообщениями объекты у нас обмениваются в Smalltalk 72.
C>Текущая реализация Erlang'а не поддерживает автоматического C>распараллеливания, однако оно возможно (что зафиксировано в стандартах C>этого языка).
Эрланг предназначен для автоматического распараллеливания не более, чем любой другой "грязный" (с побочными эффектами) функциональный язык общего назначения. Т.е. хреново он для этого предназначен, немногим лучше фортрана.
В "стандартах этого языка", которых на самом деле не существует ни одного — язык не стандартизован, это не может быть зафиксировано — спецификации языков фиксирует семантику и синтаксис, а не потенциальные возможности. Впрочем, что это я — ссылку на стандарты в студию .
AVK>>>А мне кажется что это свойство природы такое. GZ>>Нет. В природе все параллельно. Я могу идти, пить пиво, и думать одновременно.
AVK>Некорректная аналогия. Мы ведь о вычислениях говорим, а не о распитии спиртных напитков. Корректная аналогия — работа сознания. А вот оно почему то в норме не подвержено раздвоению, разтроению и т.д. Если же фоновое выполнение жизненно необходимо (дыхание, ходьба, етц) то природа пользуется "аппаратным сопроцессором" ака спинным мозгом. А вот так чтобы массовый параллелизм я в природе не припомню.
Правильно! Хорошая аналогия, то, что нужно.
В голове мысли в общем-то непараллельны, но очень асинхронны. Очень похоже на ThreadPool, особенно если ещё учесть Closures. Или "контексты" можно назвать.
Подумал кусочек одной мысли, бросил. Подумал ещё кусочек, бросил. Поднял предыдущую, подумал, бросил. Итеративно.
Такие вещи во-первых и на одном процессоре нормально работают, и оптимизируются на мультипроцесорные варианты очень неплохо. Особенно хорошо, что есть материал для эвристик: объём данных в Closures, например.
Возможно, будущее за языками, хорошо описывающими такие "разрываемые" процессы. И за компиляторами и runtime, умело оптимизирующими места разрыва и локализацию "кусочков" между исполняющими узлами.
GZ>> Вопрос в том, что сознательное мышление однопроцессорно.
AVK>Не думал о том почему?
Нет, сознательное мышление не однопроцессорно.
Просто при воспоминании мы выбираем ту "нить мысли", которую нужно. Логически она целостна, последовательна, монолитна. Но если проследить как реально всё происходит, то мысли очень сумбурны.
Так, какой-то древний грек рекомендовал заучивать поэму, ходя по саду.
Если бы потом он стал вспоминать поэму, он бы "вытащил" из своего прошлого только ниточку поэмы. Но в реальности там была не ниточка, а лоскуток ткани, с разными мохрами и волоконцами мелких мыслишек, цепляющихся за деревья, калитку, дырявую бочку у забора. В принципе, он может вытащить и другую ниточку, если, например, попытается по памяти описать свой сад подвернувшимуся вдруг покупателю недвижимости.
Здравствуйте, AndrewVK, Вы писали:
AVK>>>А смысл? Все равно выборка токенов и их обработка в LL(1) производится последовательно. GZ>>Не обязательно. Пока выделяется нода AST дерева, scanner ищет следующий токен. AVK>Больше потеряешь на синхронизации.
В случае синхронизации через очередь, потери минимальны.
AVK>>>Она и так конвеерная, только каждый шаг в случае LL(1) зависит от предыдущего. GZ>>В процах то же самое. Все зависит от предыдущего. AVK>Здорово. Аргументы будут?
В каком смысле? Торможение на jmp на PIV подойдут?
GZ>> Только если иметь еще статистику(а статистика достаточно верная вещь), то можно построить и предсказательную логику. AVK>Не путай теплое с мягким — предсказания нужны для спекулятивного выполнения, а не для разруливания зависимостей по данным.
Извини, можешь разьяснить что такое спекулятивное выполнение.
AVK>>>А мне кажется что это свойство природы такое. GZ>>Нет. В природе все параллельно. Я могу идти, пить пиво, и думать одновременно.
AVK>Некорректная аналогия. Мы ведь о вычислениях говорим, а не о распитии спиртных напитков. Корректная аналогия — работа сознания. А вот оно почему то в норме не подвержено раздвоению, разтроению и т.д. Если же фоновое выполнение жизненно необходимо (дыхание, ходьба, етц) то природа пользуется "аппаратным сопроцессором" ака спинным мозгом. А вот так чтобы массовый параллелизм я в природе не припомню.
Нее. Спинной мозг не используется при ходьбе, и формировании языка. Это то, что мы можем делать параллельно. Просто за это отвечают различные области головного мозга.
GZ>> Вопрос в том, что сознательное мышление однопроцессорно. AVK>Не думал о том почему?
Читал одну классную кижку Турчин "Феномен науки"(в сети валяется, если что напиши на мыло сброшу). Там интересная филосовская концепция метапереходов. В результате эволюционного развития, мы развились и совершили метапереход такой, что научились моделировать. Появился у нас такой слой нервных клеток. Именно это нас отличает от животных. Фактически, если следовать его логике и человечество само себя не пришибет раньше, то мы будет эволюционировать увеличивая количество одновременных моделей которые мы можем придумывать. И затем, получим некоторый метапереход, когда сможем управлять системами моделей.
Но эволюция дело долгое, а вот программирование развивается значительно быстрей. Уже давно не только наука развивает компьютеры, но и компьютеры развивают науку решая задачи которые невозможно решить нашему однопроцессорному мозгу.
Здравствуйте, GlebZ, Вы писали:
AVK>>Больше потеряешь на синхронизации. GZ>В случае синхронизации через очередь, потери минимальны.
Да нет. Придется блокировать добавление токенов в очередь как минимум. Учитывая микроскопичность выигрыша от такого параллелизма будут только тормоза
AVK>>>>Она и так конвеерная, только каждый шаг в случае LL(1) зависит от предыдущего. GZ>>>В процах то же самое. Все зависит от предыдущего. AVK>>Здорово. Аргументы будут? GZ>В каком смысле? Торможение на jmp на PIV подойдут?
И что торможение на jmp?
AVK>>Не путай теплое с мягким — предсказания нужны для спекулятивного выполнения, а не для разруливания зависимостей по данным. GZ>Извини, можешь разьяснить что такое спекулятивное выполнение.
Выполнение сразу нескольких веток ветвления.
GZ>Читал одну классную кижку Турчин "Феномен науки"(в сети валяется, если что напиши на мыло сброшу). Там интересная филосовская концепция метапереходов. В результате эволюционного развития, мы развились и совершили метапереход такой, что научились моделировать. Появился у нас такой слой нервных клеток. Именно это нас отличает от животных. Фактически, если следовать его логике и человечество само себя не пришибет раньше, то мы будет эволюционировать увеличивая количество одновременных моделей которые мы можем придумывать. И затем, получим некоторый метапереход, когда сможем управлять системами моделей.
Здравствуйте, eao197, Вы писали:
E>А вообще-то в другой ветке мы с Mamut-ом заговорили об одном, а здесь Коденок все свел к железу и одному компьютеру (пусть даже и многопроцессорному). E>Тема из Concurent и Distributed Programming ушла в Concurent и Parallel Computing, имхо.
Ага, так оно и есть. Просто про Distributed я вообще не в курсе. Да и не очень интересно. Интересны именно ПК: как он изменится и как изменится программирование на нём.
Здравствуйте, AndrewVK, Вы писали:
AVK>Некорректная аналогия. Мы ведь о вычислениях говорим, а не о распитии спиртных напитков. Корректная аналогия — работа сознания. А вот оно почему то в норме не подвержено раздвоению, разтроению и т.д. Если же фоновое выполнение жизненно необходимо (дыхание, ходьба, етц) то природа пользуется "аппаратным сопроцессором" ака спинным мозгом. А вот так чтобы массовый параллелизм я в природе не припомню.
Ну, разве что сообщества — муравейник, пчелиный рой. Они демонстрирут на диво согласованное поведение и успешно решают довольно сложные задачи. При этом сложность элементов весьма ограничено.
1.1.4 stable rev. 510
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, GlebZ, Вы писали: LCR>>Короче, чтобы воспользоваться параллельными вычислениями, нужно заменить алгоритм. (Например, взять для этой задачи алгоритм Luby: http://www.dcg.ethz.ch/members/pascal/refs/mis_1986_luby.pdf). GZ>Абсолютно правильно. Но штука в следующем, последовательные алгоритмы на параллельном процессоре можно выполнить. А вот парралельные алгоритмы на простом проце, уже трудно.
Как раз наоборот. Эмуляция многозадачности на однопроцессорной машине известна давно. А вот методы для распараллеливания произвольного кода мне неизвестны.
1.1.4 stable rev. 510
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Кодёнок, Вы писали:
Кё>Ага, так оно и есть. Просто про Distributed я вообще не в курсе. Да и не очень интересно. Интересны именно ПК: как он изменится и как изменится программирование на нём.
А вот это ты зря. Веб-программирование спровоцировало целый бум, это стало новым направлением в программировании. Но это уже вчерашний день. Сегодня мы имеем миллионы компьютеров, объединенных в сразличные сети. И это дает возможность для нового класса программ -- распределенных. Если утрировать, то представь себе, что ты запускаешь Word, но на твоей машине установлена только малая его часть. Проверку орфографии может осуществлять компонент, расположенный на каком-то другом специализированном сервере. Перевод -- опять обращение к другому компоненту. Поиск -- в гугль. И все это прозрачно как для тебя, так и для программиста, создававшего этот распределенный Word.
А вот почему эта тема отличается от просто Parallel Computing? Да потому, что там масса вопросов, связанных именно с распределенностью. Ну представь, что распределенные приложения создаются на managed-языках. Следовательно, не нужные объекты должны удаляться сборкой мусора. Но как провести эту сборку мусора, если отдельные части приложения крутятся на совершенно разных серверах? Да еще при учете возможных сбоев в коммуникационных сетях.
SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Кё>Исходный вопрос был о ситуациях, когда параллелить НУЖНО (имеет смысл).
Я бы не отказался от такого варианта при разработке БОЛЬШИХ проектов :
В Visual Studio (для примера, в общем случае — любая IDE) один процессор(ядро) отвечает за работу IDE, обработку моего ввода и пр.
(как сейчас на однопроцессорном\одноядерном десктопе), в это время другой процессор(ядро), например, может компилить часть проекта, или следить за
синхронизацией проекта (если над ним работают несколько программистов), либо ещё что-то делать из дорогостоящих операций...
+ ещё бы возможности ручного распределения спектра возможных задач среды разработки по процессорам (ядрам)
Здравствуйте, Sinclair, Вы писали:
S>Как раз наоборот. Эмуляция многозадачности на однопроцессорной машине известна давно.
Ага. Только за это приходится платить накладными расходами. S>А вот методы для распараллеливания произвольного кода мне неизвестны.
Спроси у Intel. Многоядерность с простыми RISC процами появилась, по моему, еще в первом пентюхе.
Здравствуйте, AndrewVK, Вы писали:
AVK>>>Больше потеряешь на синхронизации. GZ>>В случае синхронизации через очередь, потери минимальны. AVK>Да нет. Придется блокировать добавление токенов в очередь как минимум. Учитывая микроскопичность выигрыша от такого параллелизма будут только тормоза
Вообще-то нет. Блокируется только запись указателей.
GZ>>В каком смысле? Торможение на jmp на PIV подойдут? AVK>И что торможение на jmp? http://www.x86.org/articles/branch/branchprediction.htm
AVK>>>Не путай теплое с мягким — предсказания нужны для спекулятивного выполнения, а не для разруливания зависимостей по данным. GZ>>Извини, можешь разьяснить что такое спекулятивное выполнение. AVK>Выполнение сразу нескольких веток ветвления.
thanks. Значит мы говорим об одном и том же(или о взаимосвязанных вещах).
GZ>>Читал одну классную кижку Турчин "Феномен науки"(в сети валяется, если что напиши на мыло сброшу). Там интересная филосовская концепция метапереходов. В результате эволюционного развития, мы развились и совершили метапереход такой, что научились моделировать. Появился у нас такой слой нервных клеток. Именно это нас отличает от животных. Фактически, если следовать его логике и человечество само себя не пришибет раньше, то мы будет эволюционировать увеличивая количество одновременных моделей которые мы можем придумывать. И затем, получим некоторый метапереход, когда сможем управлять системами моделей. AVK>Это никак не отвечает на заданный вопрос.
На какой? То что мы можем в один момент мыслить только об одной вещи? Но теперь задумайся, с помощью чего. Каждый нейрон является процессорам(причем не очень быстрый). И эта мысль результат работы многопроцессорного устройства. Да и mihailik хорошо ответил.
Здравствуйте, GlebZ, Вы писали:
AVK>>Да нет. Придется блокировать добавление токенов в очередь как минимум. Учитывая микроскопичность выигрыша от такого параллелизма будут только тормоза GZ>Вообще-то нет. Блокируется только запись указателей.
Ну так добавление в очередь и есть запись указателей. Блокировка штука весьма дорогая и вполне сопоставима с временем работы лексера на тот же токен. Так что овчинка выделки не стоит. Можешь провести экспееримент. Я как то пробовал — получил 3% потерь на двухпроцессорной машине и 12% на однопроцессорной.
GZ>>>В каком смысле? Торможение на jmp на PIV подойдут? AVK>>И что торможение на jmp? GZ>http://www.x86.org/articles/branch/branchprediction.htm
И? Какое это имеет отношение к твоему утверждению, что
В процах то же самое. Все зависит от предыдущего
jmp это единстванная команда PIV?
AVK>>Выполнение сразу нескольких веток ветвления. GZ>thanks. Значит мы говорим об одном и том же(или о взаимосвязанных вещах).
Не совсем. Ветвление это весьма простой случай зависимости. Оно, грубо говоря, либо произойдет либо нет. Но уже свитч под спекулятивное выполнение не попадает, не говоря уж о зависимости по данным.
AVK>>Это никак не отвечает на заданный вопрос. GZ>На какой? То что мы можем в один момент мыслить только об одной вещи?
Именно.
GZ> Но теперь задумайся, с помощью чего. Каждый нейрон является процессорам(причем не очень быстрый).
Здравствуйте, eao197, Вы писали:
E>А вот это ты зря. Веб-программирование спровоцировало целый бум, это стало новым направлением в программировании. Но это уже вчерашний день. Сегодня мы имеем миллионы компьютеров, объединенных в сразличные сети. И это дает возможность для нового класса программ -- распределенных. Если утрировать, то представь себе, что ты запускаешь Word, но на твоей машине установлена только малая его часть. Проверку орфографии может осуществлять компонент, расположенный на каком-то другом специализированном сервере. Перевод -- опять обращение к другому компоненту. Поиск -- в гугль. И все это прозрачно как для тебя, так и для программиста, создававшего этот распределенный Word.
Эту красивую сказку с вариациями я слышу уже лет 10. Только на практике все равно основная масса ПО по прежнему все тот же десктоп. И я не вижу что с тех пор кардинально изменилось, чтобы сказка стала былью.
Здравствуйте, GlebZ, Вы писали:
S>>Как раз наоборот. Эмуляция многозадачности на однопроцессорной машине известна давно. GZ>Ага. Только за это приходится платить накладными расходами.
Многопроцессорность аппаратная тоже далеко не бесплатна.
Здравствуйте, GlebZ, Вы писали:
GZ>Здравствуйте, Sinclair, Вы писали:
S>>Как раз наоборот. Эмуляция многозадачности на однопроцессорной машине известна давно. GZ>Ага. Только за это приходится платить накладными расходами. S>>А вот методы для распараллеливания произвольного кода мне неизвестны. GZ>Спроси у Intel. Многоядерность с простыми RISC процами появилась, по моему, еще в первом пентюхе.
Вообще-то распараллеливалка на уровне процессора дает не так уж много выигрыша, если только компилятор не делает предварительную работу. Фактически, он сообщает процессору, каким образом наиболее эффективно использовать несколько ALU над заданным кодом. Я более чем уверен, что значительное увеличение количества исполнительных блоков не даст выигрыша на произвольном линейном алгоритме, т.к. анализ зависимостей становится слишком сложным.
1.1.4 stable rev. 510
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
LCR>>2. Копирование n файлов из каталога А в каталог Б. Файлы копируются по-одному, и пока не будет скопирован i-й файл, не начинается копирование i+1-го.
M>А кто мешает копировать их параллельно? Или Вы думаете, что гарантированно выжмете всю пропускную способность файловой системы и при копировании одиночных файлов?
B вот бац — закончилось место на диске. И все три файла не скопировались. Абыдна, да
Здравствуйте, AndrewVK, Вы писали:
AVK>Эту красивую сказку с вариациями я слышу уже лет 10. Только на практике все равно основная масса ПО по прежнему все тот же десктоп. И я не вижу что с тех пор кардинально изменилось, чтобы сказка стала былью.
Значит 10 лет, это слишком мало.
Насчет основной массы ПО, которое десктоп, то не берусь судить. Я больше средствами разработки занимаюсь и разработанными на их основе server-side системами. Так что, из десктопного софта я вижу, в основном, браузеры и текстовые редакторы
А вот в server-side, если систему удается прозрачно распределить по разным процессам/машинам, то это очень удобно. И здесь, мне кажется, специализированные инструменты и/или языки (вроде Erlang) должны развиваться в направлении стирания граней между монолитным и распределенным ПО.
И, если уже брать мое личное мнение по данному вопросу, то я вообще не очень верю в то, что прозрачную распределенность могут дать системы построенные на основе RPC-механизмов (когда присутствие удаленного объекта в твоем процессе имитируется наличием объекта-заменителя и скрытыми от тебя сетевыми обменами). Большая прозрачность достигается при обмене сообщениями между самостоятельными объектами-сущностями (агентами). Тогда действительно агенты легко собираются в один процесс или разносятся по разным процессам/машинам.
Но на обмене сообщениями можно делать какое-нибудь серверное ПО (вроде обработки транзакций). А вот системы вроде Word-а, имхо. затруднительно. Пример же с Word-ом я привел для иллюстрации того, к чему нужно стремиться (т.к. большинству это может быть ближе, сем server-side). Да и если что-то подобное будет достигнуто, то это будет очень эффектно, имхо.
SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Здравствуйте, Mamut, Вы писали:
LCR>>>2. Копирование n файлов из каталога А в каталог Б. Файлы копируются по-одному, и пока не будет скопирован i-й файл, не начинается копирование i+1-го.
M>>А кто мешает копировать их параллельно? Или Вы думаете, что гарантированно выжмете всю пропускную способность файловой системы и при копировании одиночных файлов?
M>B вот бац — закончилось место на диске. И все три файла не скопировались. Абыдна, да
Проблема глупых файловых систем. У них также есть другая проблема: файлы будут фрагментироваться при таком копировании, смешиваться друг с другом, что тоже не всегда хорошо. А по-хорошему можно было бы резервировать место под весь файл заранее.
Правда, это не относится к теме: жесткий диск всё равно один, так что параллелить тут вредно.
Здравствуйте, eao197, Вы писали:
E>Значит 10 лет, это слишком мало.
А, ну что ж, будем ждать.
E>И, если уже брать мое личное мнение по данному вопросу, то я вообще не очень верю в то, что прозрачную распределенность могут дать системы построенные на основе RPC-механизмов (когда присутствие удаленного объекта в твоем процессе имитируется наличием объекта-заменителя и скрытыми от тебя сетевыми обменами). Большая прозрачность достигается при обмене сообщениями между самостоятельными объектами-сущностями (агентами).
Это на самом деле пофигу. В более менее тяжелых системах все равно слой коммуникаций относительно изолированный и небольшой. И в судодейственность SOA я не верю. Гора красивых слов и демагогии, а как доходит до практического применения получается один пшик.
Здравствуйте, AndrewVK, Вы писали:
E>>Значит 10 лет, это слишком мало.
AVK>А, ну что ж, будем ждать.
Да, поживем, увидим.
E>>И, если уже брать мое личное мнение по данному вопросу, то я вообще не очень верю в то, что прозрачную распределенность могут дать системы построенные на основе RPC-механизмов (когда присутствие удаленного объекта в твоем процессе имитируется наличием объекта-заменителя и скрытыми от тебя сетевыми обменами). Большая прозрачность достигается при обмене сообщениями между самостоятельными объектами-сущностями (агентами).
AVK>Это на самом деле пофигу. В более менее тяжелых системах все равно слой коммуникаций относительно изолированный и небольшой.
Не знаю, пофигу ли. В асинхронных сообщениях есть важная особенность -- неизвесно, когда оно дойдет и дойдет ли вообще. А это накладывает свою печать на разработку приложений, основанных на обмене сообщениями.
SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Здравствуйте, Mamut, Вы писали:
LCR>>>2. Копирование n файлов из каталога А в каталог Б. Файлы копируются по-одному, и пока не будет скопирован i-й файл, не начинается копирование i+1-го.
M>>А кто мешает копировать их параллельно? Или Вы думаете, что гарантированно выжмете всю пропускную способность файловой системы и при копировании одиночных файлов?
M>B вот бац — закончилось место на диске. И все три файла не скопировались. Абыдна, да
У нас в ауле перед копированием проверяют свободное место на диске и общий объем файлов. И вообще не копируют, если они не влезут. Или Вы думаете, что во всех случаях корректнее скопировать часть файлов, чем ничего?
Здравствуйте, AndrewVK, Вы писали:
E>>А это накладывает свою печать на разработку приложений, основанных на обмене сообщениями.
AVK>Ага, и печать называется куча гемороя.
Дык, а с другой стороны-то что?:
И в судодейственность SOA я не верю. Гора красивых слов и демагогии, а как доходит до практического применения получается один пшик.
Шило на мыло, однако
SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Здравствуйте, А почему вы спрашиваете, Вы писали:
M>>У нас в ауле перед копированием проверяют свободное место на диске и общий объем файлов. И вообще не копируют, если они не влезут. Или Вы думаете, что во всех случаях корректнее скопировать часть файлов, чем ничего?
Перед глазами возникла залитая солнцем горная местность и десяток джигитов, столпившихся вокруг ноутбука
АПВ>У Вас в ауле замирает жизнь и все стоят, затаив дыхание, когда Вы начинаете копировать файлы?
Я же сказал, по-хорошему надо сразу резервировать место под весь файл. Это должна быть фича операционной системы, которая помечает секторы как занятые и работает очень быстро. Тогда процессы, встревающие в середине копирования вашего файла не будут ничего фрагментировать.
Здравствуйте, Кодёнок, Вы писали:
Кё>Я же сказал, по-хорошему надо сразу резервировать место под весь файл. Это должна быть фича операционной системы, которая помечает секторы как занятые и работает очень быстро. Тогда процессы, встревающие в середине копирования вашего файла не будут ничего фрагментировать.
Это не всегда возможно. Например, "дырявый" файл занимает физически меньше чем логически.
Здравствуйте, А почему вы спрашиваете, Вы писали:
АПВ>Здравствуйте, mik1, Вы писали:
M>>У нас в ауле перед копированием проверяют свободное место на диске и общий объем файлов. И вообще не копируют, если они не влезут. Или Вы думаете, что во всех случаях корректнее скопировать часть файлов, чем ничего?
АПВ>У Вас в ауле замирает жизнь и все стоят, затаив дыхание, когда Вы начинаете копировать файлы?
Так и знал, что кто-нибудь спросит об этом. А ответ был выше:
Есть две стратегии копирования
1)когда нужно скопировать хоть что-то (например, когда кучу скачанного надо с работы домой тащить )
2)когда нужно скопировать все или ничего (например, при накате обновления программного обеспечения)
Параллельно копировать можно в обоих случаях. Но, в первом это надо делать не жадно (хотя, если свободного места на диске очень много — можно и жадно). Во втором — можно наплодить очень много потоков копирования. Ведь если сделать копию всех файлов не удасться — это приравнивается к неудаче и все наши файлы надо будет удалять с результирующего диска.
Здравствуйте, Andrei N.Sobchuck, Вы писали:
ANS>Здравствуйте, Кодёнок, Вы писали:
Кё>>Я же сказал, по-хорошему надо сразу резервировать место под весь файл. Это должна быть фича операционной системы, которая помечает секторы как занятые и работает очень быстро. Тогда процессы, встревающие в середине копирования вашего файла не будут ничего фрагментировать.
ANS>Это не всегда возможно. Например, "дырявый" файл занимает физически меньше чем логически.
Давным-давно слышал про поддержку sparse-файлов в NTFS. И ни разу не встречал приложений, использующих их. Подскажите, для расширения кругозора?
Здравствуйте, mik1, Вы писали:
M>Параллельно копировать можно в обоих случаях. Но, в первом это надо делать не жадно (хотя, если свободного места на диске очень много — можно и жадно). Во втором — можно наплодить очень много потоков копирования. Ведь если сделать копию всех файлов не удасться — это приравнивается к неудаче и все наши файлы надо будет удалять с результирующего диска.
Просто имена к файлам нужно прилинковывать в конце по факту копирования.
Здравствуйте, Andrei N.Sobchuck, Вы писали:
ANS>Здравствуйте, mik1, Вы писали:
M>>Параллельно копировать можно в обоих случаях. Но, в первом это надо делать не жадно (хотя, если свободного места на диске очень много — можно и жадно). Во втором — можно наплодить очень много потоков копирования. Ведь если сделать копию всех файлов не удасться — это приравнивается к неудаче и все наши файлы надо будет удалять с результирующего диска.
ANS>Просто имена к файлам нужно прилинковывать в конце по факту копирования.
Это как? В CreateFile ничего подобного не помню.
А *nix мне, к сожалению, менее интересен, так как пользователи, увы — в Выньдоуз.
Здравствуйте, AndrewVK, Вы писали:
AVK>Ну так добавление в очередь и есть запись указателей. Блокировка штука весьма дорогая и вполне сопоставима с временем работы лексера на тот же токен. Так что овчинка выделки не стоит. Можешь провести экспееримент. Я как то пробовал — получил 3% потерь на двухпроцессорной машине и 12% на однопроцессорной.
Во первых, относительно чего?
Во-вторых, примитивы синхронизации InterlockedXXXX, мягко говоря, слишком неудовлетворительный список. И вообще, лучше не говорить о реализации платформы, поскольку ее и спрогнозировать сложно.
GZ>>>>В каком смысле? Торможение на jmp на PIV подойдут? AVK>>>И что торможение на jmp? GZ>>http://www.x86.org/articles/branch/branchprediction.htm AVK>И? Какое это имеет отношение к твоему утверждению, что AVK>
В процах то же самое. Все зависит от предыдущего
А что переходы редкая операция? Не очень. Точно также в LL(1) есть последовательности токенов. Просто иногда синтаксис нормализуют до нормальной формы Хомского(или еще кого-то). AVK>jmp это единстванная команда PIV?
Нет. Но немаловажная.
AVK>>>Выполнение сразу нескольких веток ветвления. GZ>>thanks. Значит мы говорим об одном и том же(или о взаимосвязанных вещах). AVK>Не совсем. Ветвление это весьма простой случай зависимости. Оно, грубо говоря, либо произойдет либо нет. Но уже свитч под спекулятивное выполнение не попадает, не говоря уж о зависимости по данным.
Если брать аналогию с процессорами, то он в случае первого выполнения переходит по жесткому алгоритму. Во втором проходе, прогнозирует что переход произойдет в то же место. С другой стороны, тут стоит поговорить о гранулярности. Мы что будем выполнять параллельно, switch или подпрограммы. Функцию в функциональном языке типа Haskell или Clean распараллелить легко, так как там нет зависимости от глоб. данных. Но все равно, без помощи компилятора такое вряд ли возможно.
AVK>>>Это никак не отвечает на заданный вопрос. GZ>>На какой? То что мы можем в один момент мыслить только об одной вещи? AVK>Именно. GZ>> Но теперь задумайся, с помощью чего. Каждый нейрон является процессорам(причем не очень быстрый). AVK>Ни в коем разе. Практически ничего общего.
Отчего — же. Мы делаем одну задачу, но множеством процессоров. Нейрон — между прочим достаточно сложный процессор. И насколько я помню — дискретный. Что в этом такого? Нормальное поведение природы. Для нее не свойственны абстракции и сферические лошади в вакууме. Она учитывает все что есть в один момент времени.
Здравствуйте, Sinclair, Вы писали:
GZ>>Спроси у Intel. Многоядерность с простыми RISC процами появилась, по моему, еще в первом пентюхе. S>Вообще-то распараллеливалка на уровне процессора дает не так уж много выигрыша, если только компилятор не делает предварительную работу. Фактически, он сообщает процессору, каким образом наиболее эффективно использовать несколько ALU над заданным кодом. Я более чем уверен, что значительное увеличение количества исполнительных блоков не даст выигрыша на произвольном линейном алгоритме, т.к. анализ зависимостей становится слишком сложным.
Как бы логично. Но вполне достаточно чтобы эффективно выполнять линейные программы. Но честно говоря — уже сейчас основное торможение идет на работе одновременной работе нескольких процессов. И в 90 процентов случаев мощность процессора для одного процесса избыточна.
Здравствуйте, Кодёнок, Вы писали:
Кё>Я же сказал, по-хорошему надо сразу резервировать место под весь файл. Это должна быть фича операционной системы, которая помечает секторы как занятые и работает очень быстро.
Здравствуйте, GlebZ, Вы писали:
AVK>>Ну так добавление в очередь и есть запись указателей. Блокировка штука весьма дорогая и вполне сопоставима с временем работы лексера на тот же токен. Так что овчинка выделки не стоит. Можешь провести экспееримент. Я как то пробовал — получил 3% потерь на двухпроцессорной машине и 12% на однопроцессорной. GZ>Во первых, относительно чего?
Относительно последовательного варианта.
GZ>Во-вторых, примитивы синхронизации InterlockedXXXX, мягко говоря, слишком неудовлетворительный список. И вообще, лучше не говорить о реализации платформы, поскольку ее и спрогнозировать сложно.
Не думаю что это сильно спасет.
AVK>>
В процах то же самое. Все зависит от предыдущего
GZ>А что переходы редкая операция?
Знаешь, между нередкая и любая большая большая разница.
GZ> С другой стороны, тут стоит поговорить о гранулярности. Мы что будем выполнять параллельно, switch или подпрограммы.
Разница существенная — по ветвлению у тебя ровно два инварианта — пойдет и не пойдет. А на свитче у тебя уже их много. А если там еще и вычисляется что то, то у тебя количество инвариантов для int к примеру — 4 миллиарда, следовательно вероятность успешного предсказания существенно падает, а статистика растет.
GZ> Функцию в функциональном языке типа Haskell или Clean распараллелить легко,
Языком. Еще раз — если алгоритм связанный, то его нельзя эффективно выполнять параллельно, вне запвисимости от того в каком стиле он записан, функциональном, императивном или каком то еще. Единственное что позволяют функциональные языки это уменьшить количество синхронизаций за счет создания копий данных. А это можно и в императивном языке явно сказать. Приемчики вроде foreach (X element in list.ToArray()) широко известны. Эту работу даже можно возложить на компилятор или JIT. Но это не приблизит нас к автоматическому распараллеливанию ни на шаг.
GZ>>> Но теперь задумайся, с помощью чего. Каждый нейрон является процессорам(причем не очень быстрый). AVK>>Ни в коем разе. Практически ничего общего. GZ>Отчего — же. Мы делаем одну задачу, но множеством процессоров. Нейрон — между прочим достаточно сложный процессор.
Ну точно таким же манером я могу назвать процессором каждый транзистор. Ну или, для полноты аналогий, каждый элементарный автомат вроде одноразрядного сумматора. Пойми — если мы говорим о логических проблемах бессмысленно углубляться в физические среды. Проблемы распараллеливания одни и те же, вне зависимости от того, что у тебя физически считает — транзисторы, радиолампы или реле. Да, конечно, базис у нейронных вычислений другой, но то что базис существенно влияет на возможность распараллеливания еще надо доказать.
GZ> И насколько я помню — дискретный. Что в этом такого? Нормальное поведение природы. Для нее не свойственны абстракции и сферические лошади в вакууме. Она учитывает все что есть в один момент времени.
Здорово. Но доказательства почему каждый нейрон это процессор, а мозг это массово-параллельный вычислитель я так и не увидел. И не увижу, поскольку как мозг функционирует, за исключением совсем простых вещей вроде управления дыханием, до сих пор не известно. Так что лучше обходись в доказательствах без аналогий.
Здравствуйте, AndrewVK, Вы писали:
AVK> Да, конечно, базис у нейронных вычислений другой, но то что базис существенно влияет на возможность распараллеливания еще надо доказать.
Ничего доказывать не буду, просто 2 маленьких частных вопроса. 1) Где в мозгу тактовый генератор, и 2) есть ли корреляция между хорошим зрением (читай "графика высокого разрешения" ) и умственными способностями (производительностью):
Сдается мне, разница поглубже, чем просто разница в элементной базе. И ряд задач точно решается параллельно (хотя бы распознавание изображений).
M>>>А кто мешает копировать их параллельно? Или Вы думаете, что гарантированно выжмете всю пропускную способность файловой системы и при копировании одиночных файлов?
M>>B вот бац — закончилось место на диске. И все три файла не скопировались. Абыдна, да
M>У нас в ауле перед копированием проверяют свободное место на диске и общий объем файлов. И вообще не копируют, если они не влезут. Или Вы думаете, что во всех случаях корректнее скопировать часть файлов, чем ничего?
А теперь взмем еще пару процессов, которые работают с диском, пару свап файлов от разных приложений (например, Фотошоп и Макромедийные продукты) и оп-па, а место-то и закончилось
Здравствуйте, Programmierer AG, Вы писали:
PA>1) Где в мозгу тактовый генератор, и 2) есть ли корреляция между хорошим зрением (читай "графика высокого разрешения" ) и умственными способностями (производительностью):
Понятия не имею.
PA>Сдается мне, разница поглубже, чем просто разница в элементной базе.
Да еще никому неизвестна. Потому и предлагаю от негодных аналогий воздержаться.
PA> И ряд задач точно решается параллельно (хотя бы распознавание изображений).
Так в обычном PC тоже много чего параллельно делается.
Здравствуйте, mik1, Вы писали:
M>Давным-давно слышал про поддержку sparse-файлов в NTFS. И ни разу не встречал приложений, использующих их. Подскажите, для расширения кругозора?
Здравствуйте, AndrewVK, Вы писали:
GZ>> С другой стороны, тут стоит поговорить о гранулярности. Мы что будем выполнять параллельно, switch или подпрограммы. AVK>Разница существенная — по ветвлению у тебя ровно два инварианта — пойдет и не пойдет. А на свитче у тебя уже их много. А если там еще и вычисляется что то, то у тебя количество инвариантов для int к примеру — 4 миллиарда, следовательно вероятность успешного предсказания существенно падает, а статистика растет.
Ну вероятность, точно такая же как и у ja. И jmp можно делать по переменной. Ничего кардинально особенного здесь особо нет.
GZ>> Функцию в функциональном языке типа Haskell или Clean распараллелить легко, AVK>Языком. Еще раз — если алгоритм связанный, то его нельзя эффективно выполнять параллельно, вне запвисимости от того в каком стиле он записан, функциональном, императивном или каком то еще. Единственное что позволяют функциональные языки это уменьшить количество синхронизаций за счет создания копий данных. А это можно и в императивном языке явно сказать. Приемчики вроде foreach (X element in list.ToArray()) широко известны. Эту работу даже можно возложить на компилятор или JIT. Но это не приблизит нас к автоматическому распараллеливанию ни на шаг.
При сегодняшней алгоритмике, конечно нет.
GZ>>>> Но теперь задумайся, с помощью чего. Каждый нейрон является процессорам(причем не очень быстрый). AVK>>>Ни в коем разе. Практически ничего общего. GZ>>Отчего — же. Мы делаем одну задачу, но множеством процессоров. Нейрон — между прочим достаточно сложный процессор. AVK>Ну точно таким же манером я могу назвать процессором каждый транзистор. Ну или, для полноты аналогий, каждый элементарный автомат вроде одноразрядного сумматора. Пойми — если мы говорим о логических проблемах бессмысленно углубляться в физические среды. Проблемы распараллеливания одни и те же, вне зависимости от того, что у тебя физически считает — транзисторы, радиолампы или реле. Да, конечно, базис у нейронных вычислений другой, но то что базис существенно влияет на возможность распараллеливания еще надо доказать.
Из Турчина.
Отметим еще одно обстоятельство, которое следует учитывать при поисках иерархии в реальной нервной сети. Если мы видим нейрон, соединенный синапсами с сотней рецепторов, то это еще не значит, что он фиксирует какое-то простое понятие первого уровня типа суммарного числа возбуждений рецепторов. Логическая функция, связывающая состояние нейрона с состоянием рецепторов, может быть весьма сложной и имеющей собственную иерархическую структуру.
GZ>> И насколько я помню — дискретный. Что в этом такого? Нормальное поведение природы. Для нее не свойственны абстракции и сферические лошади в вакууме. Она учитывает все что есть в один момент времени. AVK>Здорово. Но доказательства почему каждый нейрон это процессор, а мозг это массово-параллельный вычислитель я так и не увидел. И не увижу, поскольку как мозг функционирует, за исключением совсем простых вещей вроде управления дыханием, до сих пор не известно. Так что лучше обходись в доказательствах без аналогий.
Ну, все таки, мы кое что знаем. И в принципе достаточно чтобы сделать некоторые выводы. Иерархия понятий
Я все таки нашел Турчина в сети. Стоит заметить, что иерархия понятий нижнего уровня высчитывается параллельно и результируется на верхнем уровне.
Будет время, почитай. Чрезвычайно интересная книжка.
Здравствуйте, GlebZ, Вы писали:
GZ>При сегодняшней алгоритмике, конечно нет.
Ты так и не доказал, что для некоего зависимого алгоритма всегда (ну или хотя бы чаще) существует эквивалентный независимый. Перефразируя — а она существует, эта алгоритмика?
GZ>Из Турчина.
Я уж думал мы договорились без аналогий. Обсуждать мозг я не хочу, здесь это оффтопик.
GZ>Ну, все таки, мы кое что знаем.
Что касаемо высшей нервной деятельности, то практически ничего.
Я не верю, что пошаговая инструкция для одного исполнителя в общем случае может быть переделана в инструкцию для нескольких исполнителей без полного анализа её смысла и переписывания.
quicksort =: (($:@(<#[),(=#[),$:@(>#[)) ({~ ?@#)) ^: (1<#)
1.1.4 stable rev. 510
В отличие от механизмов которые мы умеем делать.
.
