Comments 68
должна существовать, как и в случае последовательных алгоритмов
А с чего вы решили, что для последовательнх алгоритмов это существует? Машина Тьюрига - это чистая математическая абстракция, которой не существует в реальном мире.
Или речь идет о чем-то другом?
Речь именно об этом. МТ не "сферический конь в вакууме", а модель того, чем Вы занимаетесь. Если Вы программист конечно.
Я реальный программиста, а не сферический в вакууме, и понимаю различия между математической теорией и реальностью, в которой отсутствует бесконечная память и неограниченное время при работе реальных алгоритмов.
Ну, так если "реальный" и все понимаете, то для Вас не проблема реализовать/смоделировать "чистую математическую абстракцию" на вполне обычном и реальном компе. Или есть какие-то проблемы?
Ну, или как вариант посмотрите сюда.
Абстракции в программировании нужны для упрощения/обощения алгоритмов. Для чего нужно реализовывать "чистую математическую абстракцию"?
Я бы не назвал данную статью даже спорной. Хотя бы потому, что она содержит очевидные и прямо таки вопиющие логические ошибки.
Проблема программных ошибок - это совсем не относится к МT. Ей-то какое дело до того, что у кого-то руки растут не из того места?
А про обязательность наличия прерываний и их обработки? Это-то каким местом относится к МТ? Помнится одна из самых моих первых систем была о создании системы реального времени без прерываний. Подчеркиваю - без прерываний. Кстати, все работало в реальном проекте.
Мне кажется, что ошибки как раз у вас в рассуждениях.
Проблема программных ошибок - это совсем не относится к МT. Ей-то какое дело до того, что у кого-то руки растут не из того места?
Полностью с вами согласен, что если Agile не работает, то значит его неправильно внедрили, а если в программе есть ошибки, то это точно виноват программист.
Проблема в том, что подобный аргумент в любом техническом споре, это риторический прием не имеющий ни к науке, ни к техничке никакого отношения
А про обязательность наличия прерываний и их обработки? Это-то каким местом относится к МТ?
Вот в том то и дело, что никаким местом не относится, так как у МТ нет прерываний, тогда как они нужны для работы в реальном мире и на реальном железе (а не в математической абстракции)
Реальный мир использует множество "костылей". Один из них - обработка ошибок. Расслабляться не надо, а писать так программы, чтобы они не содержали ошибок.
Прерывание - еще один "костыль". Они прекрасно покрываются параллелизмом. Что такое прерывание? Это процесс, запущенный параллельно текущему процессу по какому-то событию. В чем проблема отследить это событие? В чем проблема, чтобы отследив, запустить параллельный процесс, обрабатывающий его?
Воды много, смысла около ноля. Приплели к чему-то MATLAB и UML. Зачем, о чём...
Под многопоточностью научной базы нет. Из-за этого ее будущность весьма туманна.
"8 бит хватит всем!"
Многопоточность - весьма старый и весьма популярный механизм, вон, даже спецально обученное железо есть с поддержкой. Что здесь туманного?
для любой последовательной программы должен быть универсальный формальный механизм, преобразующий ее в эквивалентную параллельную программу и наоборот.
Разве этот алгоритм не очевиден? Если аргументы операции зависят от результата предыдущей, запускаем эти операции последовательно, иначе параллельно. И наоборот, операции из разных потоков делаем вперемешку, по одной или небольшими группами.
А есть ли уже сейчас что-то близкое по возможностям к АП? Есть. Например, все, что связано с диаграммами Харела (State-chart) и языком UML.
Языкам уже больше 20 лет. Все операторы, что Вы пишете исполняются параллельно друг дружке. Не важно, что этот IF написан на 10 строк ниже вот этого IF. Всё равно, исполняться будут параллельно.
Одно время помню на одном из этих языков можно было писать даже системные утилиты для UNIX. Был набор библиотек ввода-вывода. Но это так и не выстрелило.
Скажите пожалуйста, а заголовки к своим статьям вы сами придумываете или вам в этом кто-то помогает?
Нравится? :)
Заголовок огонь, содержимое статьи -- УГ. Мне непонятно, как это получается у одного и того же человека.
Что характерно, вы традиционно не отвечаете на простые и прямые вопросы. Например, я бы все-таки хотел бы увидеть ответ на вопрос о моделях управления для "параллельных алгоритмов".
Спасибо хотя бы за оценку заголовка :). Ну а по поводу остального я же отвечал. И делал это не раз. Читайте мою статью/статьи про определение модели параллельного автоматного программирования (АП). Там все описано очень и очень подробно. Ссылки тоже есть. Фактически в каждой моей статье. На конкретные вопросы я всегда и с удовольствием отвечаю. Расскажу даже сейчас. Повторюсь. Не поленюсь. Только лишь из уважения к Вам ;) Но совсем кратко.
У параллельной программы - параллельное управление. У автоматной параллельной программы управление - это сеть автоматов. Ну, что еще надо? Ну, что тут непонятного? Если все же не понятно, то прочитайте статью и уже по ней задавайте вопросы. Отвечу, как уже сказал, с удовольствием. Других путей просто нет.
Читайте мою статью/статьи про определение модели параллельного автоматного программирования (АП)
Читал. Унылая муть, написанная наукоподобным языком. Советовать читать ваши статьи можно только заклятым врагам.
Там все описано очень и очень подробно.
Вы себе сильно льстите. Очень сильно.
Ну, что еще надо?
Вот что я у вас тогда пытался выяснить:
В последовательном алгоритме, согласно вашим же словам "моделью управления" являются "if, while/for, switch, goto". Значит в "параллельном алгоритме" должно быть что-то другое.
Что?
Меня интересует ответ на вопрос "Что?"
А именно примеры конструкций, которые составляют в вашем мире "модель управления параллельных алгоритмов".
Меня интересует ответ на вопрос "Что?"
Неужели только в этом проблема?
Отвечаю. Таблица переходов автомата. Она заменяет все перечисленные конструкции. Поясню. Это как разница между системами команд МТ и МП. У МП - перечисленные Вами операторы управления, у МТ их нет, но есть таблица переходов.
Теперь, надеюсь, вопрос закрыт наконец-то?
А вы могли бы раскрыть сокращения МТ и МП?
МТ, возможно, машина Тьюринга. Что такое МП у меня нет версий.
Машина Поста. Прошу прощения. Я думал это Вам известно. Мне кажется, что в той же моей статье по МТ я должен был это сокращение расшифровать.Вы читали эту статью?
Проверил. Понятие есть, вот сокращения нет. Но должно быть где-то в других статьях. Я часто его использую.
Машина Поста.
В первый раз слышу. В нашем провинциальном ВУЗе мы слышали только про машину Тьюринга и это знание, как и много из услышанного во время учебы, затем никогда больше не пригождалось на практике.
Это пробел в Вашем образовании :) Но, если серьезно. Про машину Поста, да, кажется, и МТ я узнал уже позже - самообразуясь ;) И оказалось все то, что мы используем на практике в программировании и есть в своей основе МП, а совсем не МТ. Правда для меня ситуация поменялась. Я сейчас по большей части использую МТ, а не МП. Вот до чего доводит самообразование! :)
Кстати, не удивительно, что МТ вам не пригодилась. А что скажите про конечные автоматы?
Это все пустопорожняя лирика.
У меня два конкретных вопроса.
Eсли вы считаете, что в параллельных алгоритмах моделью управления является таблица перехода, то условия, которые инициируют смену состояния автомата для вас if-ами не являются?
Можете показать, как на ваших любимых параллельных автоматах реализуется std::reduce с std::execution::par? Это ведь самое простое, что есть в параллельном программировании.
Это для Вас лирика. Но это совсем не лирика, если понимать концепцию в рамках которой Вы "существуете". Но это речь о МП. Совсем не "лирика" понимать принципиальную разницу межу МТ иМП.
С точки зрения автоматов условие переходов между состояниями - это логическая функция Реализовать функцию переходов/выходов автомата можно по-разному. В самом простом варианте я, кстати, использую if. Могу switch и т.д. Но на С++ в QT это чистая таблица переходов (ТП).
По поводу библиотеки std. Все это решается легко и просто. Если, например, вектор небольшой, то прямо так и использую (речь о reduce). Если большой, то через автоматный цикл обработаю его. Это чтобы не было тормозов в цикле обработки автоматов.
По поводу std::execution::par. Подобный параллелизм мне чужд :) Вы же это должны понимать? Все будет определяться конкретной задачей. Хотя, если припрет, так сказать, то могу влепить и это "чуждую" мне конструкцию. Проблем не вижу. Но, думаю, они будут, если "влеплю", как я сказал. Поэтому, скорее, это будет происходить в силу каких-то непредвиденных обстоятельств. Например, под "дулом автомата" :)
Попробовал пофантазировать на тему. Создам параллельно моим автоматам обычный поток. Против потоков я ни-ни, т.к. иногда тоже ими пользуюсь. Ну, когда "припрет". А уже в этот поток "влеплю" предлагаемую Вами конструкцию. Думаю, что будет именно так.
Да. А про автоматы Вы что-то промолчали. Как с ними-то?
Это для Вас лирика
Лирика -- это рассуждать о самообразовании.
С точки зрения автоматов условие переходов между состояниями - это логическая функция
А эта фраза всего лишь сотрясение воздуха. В последовательном алгоритме вы вынуждены писать if-ы с условиями для того, чтобы идти по одной из ветвей. В описании автомата вы вынуждены навешивать условия на переходы между состояниями для того, чтобы идти по "одной из ветвей".
Т.е. условия и реакции на них у вас будут все равно. Возьмите, для примера, алгоритм двоичного поиска: вам нужно имея (l, r) вычислить m, затем сравнить v[m] с искомым, затем изменить пару (l, r) в зависимости от результата сравнения.
В привычном для обычных людей последовательном алгоритме мы будем иметь простые if-ы и while (или if-ы и goto). Могу предположить, что в воображемом вами мире параллельных алгоритмов на параллельных автоматах все те же самые условия "повиснут" на переходах между состояниями какого-то КА.
Т.е. от условий и следованию условиям вы никуда не денетесь. Оформлять их разве что будете другим образом. И если для вас этот "другой образ" (который вы назваете "моделью управления") настолько принципиально важен, то OK. Может быть это хоть как-то объснит упоротость ваших возрений.
Подобный параллелизм мне чужд :)
Остается только повторить то, что я уже говорил в комментариях к вашим статьям: вы предлагаете избавляться от проблем параллельного программирования отказом от самого параллельного программирования.
А значит придется повторить и другую вещь, которая так же высказывалась: вы пытаетесь рассуждать о вещах, в которых не разбираетесь. Ну вот не занимаетесь вы параллельным программированием. Нет у вас в этом опыта (что следует из общения с вами и из ваших статей). Не знаете вы что это за мир.
Но поднимаете флаг правдоруба и несетесь вперед с окрытым забралом с какой-то ахинеей. Зачем?
Зачем?
Затем, что я предлагаю определенную модель параллельного программирования. Я строго доказал, что это модель именно параллельного программирования. Я показал и доказал, что можно считать моделью параллельного программирования. Пока мои доказательства ни кто не опровергнул. В том числе и Вы. Я даже смею утверждать, что то программирование, за которое Вы так бьетесь не является параллельным. Это почти азы теории программирования. Кроме Ваших эмоций в мой адрес, каких-то других аргументов и доказательств я не вижу и не слышу.
Давайте от эмоций переходить к аргументам. Ну, например, глядя на любую программу Вы сможете определить/оценить ее степень параллелизма?
Надеюсь, что наберетесь смелости и ответственности, чтобы ответить хотя бы на этот вопрос. По сути, это простой вопрос. Но, конечно, аргументированно. Если, конечно, такие аргументы у Вас найдутся.
Выше я писал отсылки на VHDL/Verilog
А если есть последовательное программирование, то должно быть, как его ни назови, альтернативное ему - параллельное. А если уж оно есть или, как минимум, обсуждается, то необходимо дать ему определение, аналогичное по смыслу моделями обычных алгоритмов.
здесь есть изъян рассуждения. Чтобы его ХОРОШО видеть, Вам стоит попробовать попрограммировать на этих самых VHDL/Verilog (или что там есть на эту тему современное - я просто этим занимался около 20 лет назад, потому в современном состоянии не очень в курсе).
Так вот, представьте язык, в котором Вы пишете сверху вниз два IF, пару присвоений и затем ещё один IF. А исполняются ВСЕ эти операторы параллельно друг дружке и одновременно.
И вот попытавшись воспользоваться таким языком Вы сразу же сталкиваетесь с философским (именно философским!) тезисом: вся наша вселенная, весь наш мир основаны на причинно-следственных цепочках:
В атом урана 235 влетел нейтрон и атом развалился на два более лёгких атома и три нейтрона.
Встретились мальчик и девочка, а через какое-то время у них появилась проблема, за которую нынешнее государство выплатит девочке 150 тыс руб
и так далее.
Так вот все эти цепочки (примеров коих тыщи) они всегда (ВСЕГДА) последовательные во времени. Сперва в атом врезается нейтрон. Затем через время атом разваливается на две части. Затем три высвобожденных нейтрона летят некоторое время к другим атомам. И так далее.
Если это моделировать на параллельном языке, вроде VHDL/Verilog то приходится в чисто параллельный язык вкладывать операторы, которые будут устанавливать причинно-следственную зависимость, которая будет выражаться именно в последовательном выполнении операторов.
И вот если дальше на эту физическую или философскую проблему смотреть, то в мире алгоритмов будет огромное количество последовательных алгоритмов, которые можно запускать параллельно друг дружке. 99% кода - описаны последовательно, а оставшийся 1% - параллельно.
И вот благодаря этому факту утилиты для UNIX, вебсервера и так далее пишутся на Python/C/Lua/PHP/Rust/итп, а не на Verilog/VHDL. А Verilog/VHDL остаётся нишевым для программирования всяких ASIC/PLD.
PS: как по мне, обычный язык со стекфул гринтредами - нечто близкое к идеалу с точки зрения адекватности модели мира.
PS: Есть Golang, но как по мне, в нём сделали огромную ошибку: сделав горутины вытесняемыми (параллельными). Из-за этого внеся проблемы планировщика OS внутрь языка.
Все можно описать гораздо короче и точнее.
Есть мир, в котором существуют множество объектов. Эти объекты "живут" одновременно. Они как-то взаимодействуют друг с другом. Причем в любом количестве и на любом расстоянии. Это грубая картина. Добавляем в мир "приправу" - время. А в каком времени они живут? Я так считаю в одном. Вот модель на уровне объектов. Параллельных объектов.
Модель отдельного объекта. Вот она последовательна. Дискретная кибернетика предлагает в качестве его модели автомат. Я согласен.
Вот и весь "кибернетический мир". Объект - автомат. Много объектов сеть автоматов. Время общее и единое. Значит сеть синхронная и в едином времени.
Все! Подходит такая картина? Дальше придумываем языки для описания этого мира. Поскольку объект - автомат, то и язык соответствующий. Вот "на пальцах" модель реального мира в рамках АП (реализация - ВКПа).
Вы можете предложить свою модель мира и языки его описания. В том числе и упомянутые Вами. Я бы предложил аналог - А-схемы программ: все операторы параллельны, а хаос их работы упорядочивается специальными операторами.
Все, что Вы описали пройдено мною вдоль и поперек. Так в чем тут "изъян"? В модели мира. В модели объекта и его языке его описания?
Все, что Вы описали пройдено мною вдоль и поперек. Так в чем тут "изъян"?
в необходимости это [пере]проходить
человечество не тупое. поскольку мир состоит из множества (да, параллельно живущих, но всё же) причинно-следственных цепочек, то получается что на программирование собственно цепочек нужно 99% усилий, а на программирование их параллельности - 1%.
а потому языки с параллельной парадигмой тупо в 99% случаев не нужны.
они есть, их изобрели ещё в 80е годы прошлого века (если не раньше), но они крайне нишево востребованы.
То, куда Вы копаете, - штука очень нишевая. Подходит для ASIC/PLD, но будет вызывать лютый оверхед при написании, например, серверных программ.
Интересный момент!
получается что на программирование собственно цепочек нужно 99% усилий, а на программирование их параллельности - 1%.
Откуда взялись такие оценки? Я "тупо" с ними не согласен. Как не согласен и с последующим выводом :)
Итак. Поясните. Но поскольку, как мне показалось, это будет интересный разговор, давайте перейдем на верхний уровень обсуждения. Ваш ответ я буду ждать там (для этого переместитесь в конец обсуждения и создайте там коммент).
Откуда взялись такие оценки? Я "тупо" с ними не согласен. Как не согласен и с последующим выводом :)
давайте ещё раз от истоков пойдём.
итак, современный процессор устроен следующим образом:
есть память программ. программа - это текст, написанный сверху-вниз (иногда с пересылками). И процессор из этой памяти программ выбирает команды "по одной" и все их выполняет "по очереди".
Уж не знаю, процессоры ли подделывали под реальный мир, нас окружающий, или никакой другой абстракции придумать не смогли и сделали что получилось, но вот так.
Имеем: процессоры умеют выполнять только последовательный код.
Именно ли поэтому, либо потому что в мире наблюдается множество причинно-следственных цепочек, но это в целом не важно. Важно что написание последовательной программы в обоих случаях естественно.
И вот во всём программировании которое есть у нас очень немного областей, где требуется программирование параллельное. Вот всё что у нас есть:
множество пользовательских ПОСЛЕДОВАТЕЛЬНЫХ программ на одном компьютере (взять данные - посчитать результат);
серверное программирование: обслуживание одним сервером множества пользовательских ПОСЛЕДОВАТЕЛЬНЫХ запросов;
(о видео и нейро я поговорю отдельно, но упомяну его здесь)
есть ещё интерактивные программы, но поскольку они почти 100% времени проводят в ожидании ввода пользователя и в ответ на этот ввод снова запускают ПОСЛЕДОВАТЕЛЬНЫЕ цепочки обработки - это смело можно относить к последовательным программам (параллельность здесь не нужна)
всё
Так вот, если посмотреть в код какого-нибудь http-сервера, то в нём мы найдём EV машину, переключающую контекст между обработчиками запросов и сами обработчики запросов. Возьмите любой вебсайт, habr, например: кодовую его базу внутри обработчиков сравните с этой вот EV-машиной. Получится на параллельность уйдёт дай бог 1%. И, кстати, взаимодействия между параллельными процессами Вы почти что и не найдёте (мой запрос в реальном времени никогда не взаимодействует с Вашим).
Теперь можно поговорить о круто-нишевых задачах: обработка видео и нейрообработка. Здесь да, требуется обсчитать 100500 точек, либо 100500 состояний нейронов и здесь бы параллельное программирование рулило и бибикало. Но поскольку иных процессоров, кроме последовательных, человечество так и не придумало, то для решения этих задач используют GPU, содержащие в себе тысячи простеньких CPU или собирают большие кластеры. Но внутри каждого GPU снова вертится последовательная программка.
Если сравнить объём кода что выполняется внутри GPU с объёмом кода на обеспечение самой параллельности - снова получится не в пользу параллельности.
как-то так
Затем, что я предлагаю определенную модель параллельного программирования.
Я ничего не понимаю в теориях, но то, что вы предлагаете в виде своего ВКП (а ваш ВКП, как я понимаю, это инструмент, реализующий вашу модель параллельного программирования), тупо не может обеспечивать параллельную и независимую работу ваших конечных автоматов. Т.е. реализованная вами же "практика" не подтверждает вашу же "теорию".
Я строго доказал, что это модель именно параллельного программирования. Я показал и доказал, что можно считать моделью параллельного программирования.
Интересно, сколько человек разделяет вашу точку зрения.
Я даже смею утверждать, что то программирование, за которое Вы так бьетесь не является параллельным.
Даже интересно за какое такое параллельное программирование я так бьюсь?
Ну, например, глядя на любую программу Вы сможете определить/оценить ее степень параллелизма?
Зачем это вообще нужно?
Давайте рассмотрим простой бытовой пример: у меня есть 60 hi-res .flac-файлов, которые я хочу перегнать в mp3. Запускаю конвертер X на машине с 12 ядрами и вижу, что все мои ядра загружены под 100%, а итоговое время конвертации -- 20 секунд. Запускаю конвертер Y в тех же самых условиях и вижу, что потребовалось 200 секунд при постоянной загрузке всего лишь одного ядра.
На этом бытовом уровне я вижу, что X использует распараллеливание (т.е. параллельное программирование имеет место быть), а Y -- нет.
... тупо не может обеспечивать параллельную и независимую работу ваших конечных автоматов.
Смотрите на мое решение задачи о философах.
Я ничего не понимаю в теориях...
Уж коли критикуете надо разбираться... А так - "не знаю, но осуждаю" ;)
Интересно, сколько человек разделяет вашу точку зрения.
Число тут совершенно не имеет значения. И, замечу, не "точка зрения", а формальное доказательство. Говорят, что теорему Перельмана понимают буквально несколько человек. До конца - возможно, он один. Я не веду такой подсчет. :)
интересно за какое такое параллельное программирование я так бьюсь?
Забыли? Многопоточное.
Зачем это вообще нужно?
Затем, чтобы задуматься - как же решить обозначенную проблему. И согласиться или предложить решение. Вы, судя по Вашему примеру, не можете предложить решение. Речь о "черном ящике". В его нутро доступа нет.
Смотрите на мое решение задачи о философах.
Нужно было добавить "до посинения". Не на что там смотреть. Ваше решение работает только потому, что вы тактируете свое модельное время и устраиваете stop-the-world после каждого такта для обновления состояния всех КА. Более того, ваши КА могут беспрепятственно читать состояния других КА. И возможно это только благодаря тому, что все у вас работает исключительно в однопотоке.
Подобная схема просто полный маразм для действительно параллельных вычислений, когда задачи распределяются по параллельно работающим ядрам, а обмен информацией между задачами сводится к самому-самому минимуму.
Уж коли критикуете надо разбираться...
Так практика является критерием проверки теории. Вы тут из статьи в статью двигаете какую-то свою теорию. Я смотрю в ВКП как в пример ее реализации и вижу, что там параллельности нет в принципе. Т.е. вы сами практикой не можете подтвердить свою же теорию.
На этом уже все, стоп, приехали. Дальше остается бросаться в вас гнилыми помидорами и гонять ссаными тряпками чтобы не несли ахинею с умным видом.
Вы занимаетесь автоматным программированием -- вот и занимайтесь. Рассказывайте о том, как применяете, какие задачи и как решаете, почему это хорошо.
Но блин, хватит нести чушь про "параллельное программирование" в общем.
И, замечу, не "точка зрения", а формальное доказательство.
Под точкой зрения я имею в виду вашу веру в то, что вы что-то сформулировали и что-то доказали. Вот мне и интересно, верит ли в это кто-то кроме вас.
Говорят, что теорему Перельмана понимают буквально несколько человек.
Но они хотя бы есть.
Затем, чтобы задуматься - как же решить обозначенную проблему.
Какую такую проблему? Я не помню, чтобы передо мной когда-либо стояла задача "определить степень параллелизма" какого-то кода или какой-то программы.
Задача ускорить обработку данных за счет распараллеливания... Вот такие задачи встречались несколько раз последние 20-25 лет (и это с учетом того, что я не занимаюсь parallel computing-ом, а разве что concurrent computing-ом). Но "определять степень параллелизма" произвольного кода... Такого не было.
Вы, судя по Вашему примеру, не можете предложить решение.
Я вообще стараюсь херней не страдать.
Вам я уже предлагал показать как будет выглядеть на вашем автоматном подходе с параллельными автоматами реализация reduce с параллельным выполнением. Вы ожидаемо не смогли. Так что это вы не можете предложить решение в рамках рекламируемой вами "модели параллельного программирования".
Нужно было добавить "до посинения"
Вы близки к оценке сколько нужно, порой, времени, чтобы понять суть задачи.
Какую такую проблему? Я не помню, чтобы передо мной когда-либо стояла задача "определить степень параллелизма" какого-то кода или какой-то программы.
А я "сщас" ее поставлю перед Вами ;). Откройте мою крайнюю статью про философов. Открыли? Посмотрите на любую "гифку". Посмотрели? А теперь, не читая статьи, чисто по внешнему поведению философов на этой самой гифке оцените степень параллелизма решения.
Ну, сколько получилось? :)
А я "сщас" ее поставлю перед Вами
Вы бы перестали херней страдать, а показали бы, как на вашем автоматном подходе реализуется std::reduce с параллельным выполнением.
Сможете?
А теперь, не читая статьи, чисто по внешнему поведению философов на этой самой гифке оцените степень параллелизма решения.
Нахера и, главное, зачем?
Зачем кому-то оценивать "степень параллелизма"?
Зачем же так грубо? Про reduce я дал Вам ответ. Чем он Вас не устраивает?
Нахера и, главное, зачем?
Я тоже могу в таком же стиле - чтобы было дохера! Вас устроит такой ответ? Думаю нет.
А вот зачем. А затем, что Вас попросили. Помните начало статьи? Вы можете, глядя на программу, оценить тип ее алгоритма? Последовательный от или параллельный. Если последовательный, то процесс один и степень, соответственно, одна. Если Вы узрели параллелизм, то сколько процессов насчитали. Сколько насчитали столько и будет степень. Насчитали "дохера" и степень будет "дохера". Ну, как - доступно объяснил "зачем"?
Зачем же так грубо?
Потому что нормального языка вы, видимо, не понимаете.
Про reduce я дал Вам ответ.
И вот это, по вашему, ответ:
По поводу std::execution::par. Подобный параллелизм мне чужд :) Вы же это должны понимать? Все будет определяться конкретной задачей. Хотя, если припрет, так сказать, то могу влепить и это "чуждую" мне конструкцию. Проблем не вижу. Но, думаю, они будут, если "влеплю", как я сказал. Поэтому, скорее, это будет происходить в силу каких-то непредвиденных обстоятельств. Например, под "дулом автомата" :)
Это смеху*чки какие-то, а не ответ.
Или может вот это ответ:
Попробовал пофантазировать на тему. Создам параллельно моим автоматам обычный поток. Против потоков я ни-ни, т.к. иногда тоже ими пользуюсь. Ну, когда "припрет". А уже в этот поток "влеплю" предлагаемую Вами конструкцию. Думаю, что будет именно так.
Вы в своих статьях поливаете многопоточность говном. Мол только ваш автоматный подход и есть правильная параллельность, а не эти ваши многопотоки, которые не имеют под собой никакой научной базы... А когда выясняется, что таки параллелить-то надо, то а почему бы и не задействовать многопоточность? Вероятно это другое, понимать надо.
Ну и да, ваш типа "ответ" -- это какая-то мутная отписка. В код reduce я и сам заглянуть могу, да и представляю что и как там будет выглядеть.
А вот код на ваших волшебных автоматах увидеть можно? Ну чтобы оценить всю прелесть и мощь.
Вы можете, глядя на программу, оценить тип ее алгоритма?
Зачем?
Сколько насчитали столько и будет степень. Насчитали "дохера" и степень будет "дохера"
Еще раз: зачем это все?
Ну, как - доступно объяснил "зачем"?
Нет. В очередной раз заставили задуматься а вменяемый ли вы вообще -- это да. Объяснений как не было, так и нет.
Объясняю для особо упоротых и игнорирующих теорию. Кто хоть немного понимает в деле, то понимает и то, что философов последовательно не решить Жизни не хватит. Почитайте Хоара. Его оценка - "два в степени 1.8 млн состояний" нужно будет как-то реализовать. Это если делать в "один хер". Если "херов" будет много и они параллельны, то реализация одного "хера" будет посильна обычному Херу :) И состояниями эти "херы" покроют одного "хера" оценочно "хер"х"хер"х"хер"... , т.е. очень дохера, а попросту дох.я!
Продолжать ликбез? Или откроете книжку Хоара, чтобы понять, в чем ценность задачи о философах и, другими словами, на кой хер она нужна. А когда поймете, то можно поговорить плотнее и на тему reduce.
Продолжать ликбез?
Нет. Вы либо признаетесь, что у вас есть справка о тяжелой болезни из психдиспансера и тогда вас перестают трогать по объективным причинам.
Либо же вы:
объясняете зачем кому-то нужно определять "степень параллелизма";
показываете реализацию reduce с параллельным выполнением на ваших хваленых параллельных автоматах.
т.е. вы перестаете вести себя как Д'Артаньян, который один такой красивый стоит в белом пОООльто. Чтобы можно было вести предметный разговор.
Переходим на нормальный язык. Насколько я понял, Хоара читать не хотите? Это чтобы вести "предметный разговор".
Нормально языка вы, видимо, не понимаете.
А реализации reduce на ваших параллельных автоматах, скорее всего, никто и никогда не увидит.
Пара слов для тех терпеливых людей, которые еще заходят прочитать здешние комментарии. Почему я вообще прицепился к автору и почему меня триггерит его манера вести разговор: использование многоядерных CPU -- это наша нынешняя реальность, отрицать которую бесполезно. Рост производительности в однопоточном режиме у современных CPU идет очень медленно, прорывов здесь ждать не приходится. Но зато количество ядер даже в недорогих ноутбуках и смартфонах неуклонно растет.
Следовательно, основной ресурс для увеличения производительности софта в современных условиях -- это использование многоядерности. Т.е. распараллеливание операций в коде программы.
А в современных ОС общего назначения (Windows, Linux, BSD, macOS и т.п.) это распараллеливание возможно за счет многопоточности, т.к. единицей диспетчеризации в таких ОС является именно тред (поток, thread).
Применение многопоточности влечет за собой кучу проблем. Именно поэтому я неоднократно в разных местах говорил и повторю еще раз: голая многопоточность -- это пот, боль и кровь. Если у вас есть возможность не использовать многопоточность, то не используйте ее.
Но, увы, выбора не использовать многопоточность практически не остается. И чем дальше, тем больше мы будем на многопоточность завязаны.
Значит, нужно изыскивать средства борьбы со сложностью параллельного программирования частным случаем которого являтся та самая многопоточность.
И тут появляется герой, который заявляет что-то вроде "херня вся эта ваша многопоточность, под ней даже никакой научной базы нет". Но это бы ладно. Главное, что есть некая волшебная модель параллельных вычислений, которая мало того, что теоритически обоснована, так еще и является полноценной альтернативой многопоточности. И вообще там все просто прекрасно и никаких связаных с многопоточностью ужасов нет. Эдакая волшебная пилюля, которую мы так ждали (это сарказм, если что).
Однако, почему-то статьи этого героя написаны так, что больше напоминают наукообразую муть, чем вменяемое описание. Да и сам герой ведет себя в комментариях как чудак на букву М, который вместо того, чтобы объяснять что к чему, отсылает читать то свои мутные опусы, то кого-то авторитетного (вот как Хоара в данном случае), правда не говорит что именно нужно прочесть.
А еще более интересно, что результат работы героя, библиотека ВКП, в которой эти самые идеи параллельного программирования на базе автоматов реализованы самим же автором, принципиально однопоточная. By design. Потому что иначе никак (у героя, ЕМНИП, даже статья была, в которой он как школьник-двоешник объяснял почему же не смог в многопоток). Т.е. громкие слова героя внезапно (опять сарказм) расходятся с делом.
Грубо говоря, если вы, как и я, интересуетесь как упростить себе жизнь когда приходится распараллеливать что-то в коде, то в работах этого автора вы ничего полезного, увы, не найдете. По следующим (как мне кажется) причинам:
Автор специализируется в своей нише автоматного программирования. Для которой эти самые модели параллельных вычислений на базе конечных автоматов являются родными и естественными. К привычному же большинству из нас параллельному программированию (примером которого и является упоминавшаяся выше
reduceс параллельным исполнением) это не имеет отношения. Но автор об этом умалчивает и упорно лезет на поляну того самого привычного нам параллельного программирования.Сами статьи малополезны, т.к. написаны плохопонимаемым наукообразным языком. И иногда кажется, что написаны они не совсем здоровым (в медицинском плане) человеком.
В комментариях автор статей ведет себя как чудак на букву М, который скорее пошлет вас что-то изучать, чем сможет дать ясный и понятный ответ на конкретный вопрос.
Т.е. к сожалению, выясняется, что если вам (как и мне) приходится жить с многопоточностью, то в работах @lws0954 вы, скорее всего, ничего полезного для себя не найдете. Не смотря на броские заголовки и манеру подачи с закосом на солидность и обстоятельность.
Ну а раз так, и раз "нам втирают какую-то дичь", то почему бы не припечатать такого героя ссаной тряпкой?
голая многопоточность -- это пот, боль и кровь. Если у вас есть возможность не использовать многопоточность, то не используйте ее.
К сожалению, это не вариант. Но и отчаиваться не нужно, так как всегда остается шанс найти более или менее нормальное решение, хотя не в рамах беседы с текущим автором :-)
Но и отчаиваться не нужно, так как всегда остается шанс найти более или менее нормальное решение
Именно это я и рекомендую делать. Т.е. вместо того, чтобы пердолится (пардон май френч) с мутеками и кондишенами самостоятельно (а то и с атомиками и самодельными lock-free конструктами), лучше взять что-то готовое и проверенное, на счем другие люди уже кучу шишек себе набили.
Ну да, в том числе и это. Хотя мне бы хотелось, чтобы была хоть какая нибудь защитная семантика на уровне исходного кода, которая бы предотвращая ошибки многопоточности во время компиляции :-)
Применение многопоточности влечет за собой кучу проблем. Именно поэтому я неоднократно в разных местах говорил и повторю еще раз: голая многопоточность -- это пот, боль и кровь. Если у вас есть возможность не использовать многопоточность, то не используйте ее.
Но, увы, выбора не использовать многопоточность практически не остается. И чем дальше, тем больше мы будем на многопоточность завязаны.
"Ржу, прям, не могу!" Я ж об этом таким, как Вы, и говорю:) Только вывод из всего Вы делаете прямо противоположный.
А Ваши "пот, боль и кровь" явно влияют на мозги, превращая в элементарного хама, малообразованного чела и "упоротого многопоточника". Поразмышляйте над этим ;)
И тут появляется герой, который заявляет что-то вроде "херня вся эта ваша многопоточность, под ней даже никакой научной базы нет".
На этом моменте я тоже очень сильно удивился. Есть всякие мультипроцессоры, примитивы синхронизации, специфические законы, модели памяти, протоколы когерентности, книжки, курсы в университетах... А тут тезис "никакой научной базы нет".
Система тасков и корутины уже большой шаг к такой многопоточности. В зависимости от количества потоков выполняющих задачи и будет однопточные или многопоточные программы. Проблема только в устаревших ОС и устаревшей кодовой базе, включая популярные либы.
Система тасков и корутины уже большой шаг к такой многопоточности.
Какой "такой"? Система тасков и корутин не является алгоритмической моделью. Даже просотй, а не то, чтобы параллельной.
Какой "такой"
Пока что единствено возможной реализацией алгоритмической медели. Проблема в том, что создатели железа адаптируют его под существующие программы, а программы выбрали путь многопоточности.
Есть еще вариант SIMD/SIMT - когда одна инструкция выполняется для набора данных, такие вот виртуальные потоки с возможностью дешевого чтения регистров соседних потоков, что позволяет наплохо так оптимизировать математику.
Происходит вполне осязаемый процесс зомбирования многопоточностью
Современная многопоточность это alter ego ... последовательного программирования.
Кажется многопоточность это просто абстракция операционной системы над реальным железом, и не более того. Мы используем её чтобы делегировать ОСи работу по переключению контекста, а как оно дальше исполняется, нас в целом не волнует. В результате использование потоков может привести либо к конкурентному исполнению (1 задача в каждый момент времени), либо к параллельному (много задач одновременно).
Как и любая другая абстракция, она нужна для удобства написания программ. Более того, многопоточность опциональная (aka "opt-in"), программист может в рантайме решить, стоит ли использовать её или нет. При параллельном исполнении программа скорее всего затратит меньше времени, что часто и является желаемым эффектом.
Я осознаю, что дальше в статье идут почти философские рассуждения, но кажется существует недопонимание терминов на базовом уровне.
Спасибо. Боле чем откровенный комментарий. Вы создали механизм, а дальше Вам наср... (пардон), напл... (еще пардон) Короче, все равно, с чем столкутся программисты. О они, как сами программисты расписывают, нешуточные. Так, чтобы изменить общую переменную из нескольких потоков нужно пройти адовы круги (см. ниже недавнюю статью на эту тему). Честно, откровенно, в лоб ... Примечательно, что некоторым программистам-мазохистам \это даже нравится :)
И тут Вы вдруг заговорили про "удобства". От кого-кого, но от Вас это звучит не то, чтобы неожиданно (хотя и это тоже), а как-то даже лицемерно что ли (не подберу сразу слово, но пусть будет так). И разве Вы не слышали, что использование многопоточности считается скорее нежелательным, чем положительным приемом. Я уж молчу про "удобства", а и выигрыша в скорости не обещают даже... Вот такой парадокс.
И по поводу "недопонимания терминов". Что тут недопонимать. Поток он и Африке поток. Ну а за остальные "термины", как я понимаю, Вы уже не в ответе. Так что с пониманием "потока" все нормально. Собственно, настолько элементарно, что тут даже понимать нечего. Недопонимать уж тем более. :)
Но... Я ж не против потоков. Иногда они очень даже к месту. Я даже использую. Но не часто, а так - больше по необходимости и, скорее, вынужденно. На безрыбье, как говорится, и щука раком станет :)
современная реализация многопоточности растёт из двух факторов:
(как обсуждалось выше) - причинно-следственного мироустройства
архитектуры современных процессоров
ну ничего пока человечество не придумало, кроме как выбирать программу из памяти по одной инструкции и эти инструкции выполнять.
Вот прям очень это важно. Выбирать по одной инструкции и по одной же и выполнять.
Когда потребовалась многозадачность, то придумали сперва многопоточность. А после многоядерность.
Так вот, многопоточность в парадигме выбора программы по одной инструкции может быть реализована двумя способами (других, увы, не придумали):
кооперативная (это когда поток передаёт другому потоку управление добровольно, когда может)
вытесняющая
И если говорить о вытесняющей, то там ничего другого, кроме как квантовать время по таймеру тоже не придумали. А вследствие этого существует такое понятие, как частота квантования и жёсткие ограничения на число потоков на одно ядро.
И вот если Вы хотите подлинно параллельный язык программирования, то Вам надо сперва что-то исправить в самой парадигме.
Поставь нам программирование аналого машин тьюринга можно рассмотреть лямбда исчисления. Да параллельного программирования Был ли придуман был придуман механизм пи исчисления.
По поводу перевода программы из последовательного алгоритма в параллельный очень хороший комментарий дал Akon32 - такая оптимизация проводится на всех этапах: от компиляции до исполнения. Увы, комментарий остался без ответа, но мнение автора на этот счёт довольно интересно
По поводу темы статьи - проблемы реализации модели двух парадигм (если это можно так назвать). Ох, тут всё намешано в кучу. Машины Тьюринга/Поста ни в коем случае не являются моделями какой-либо парадигмы. Это модели непосредственно исполнителей с неограниченным ресурсом памяти и времени. Более того, это абстрактные модели НЕРЕАЛИЗУЕМЫХ на практике исполнителей. Утверждать, что это - модели, описывающаие поведение исполнителей последовательных программ, - нельзя. Кроме того, ничего общего с ПОСЛЕДОВАТЕЛЬНЫМ исполнением здесь нет. МТ - это класс машин. Есть недетерминированная, ещё более абстрактная машина Тьюринга. Она может одновременно исполнять несколько переходов, быть в более чем одном состоянии в единицу времени. Чем не модель параллелизма? Но нет, опять же, с реальным миром это не имеет ничего общего. Как хорошо, что меня в универе этому учили целый год :)
Чтобы ответить на вопрос о том, есть ли МОДЕЛЬ какого-либо процесса, предлагаю автору грамотно построить вопрос, ЧТО является моделью? Дать ей определение, прежде чем искать
Люди, утверждающие, что МТ не имеет ничего общего с реальностью из-за каких-то исключений - встречный вопрос: вы знаете про ЯП Go/Rust? Вместо тяжёлых виртуальных таблиц прерываний они используют лёгкие и предсказуемые ветвления, с лёгкостью реализующие аналогичное поведение (можно сколько угодно спорить на тему эффективности, но к теме статьи это не относится)
P.S.: ни в коем случае, не хочу никого обидеть - желаю только справедливости и хочу сам разобраться в теме. Безусловно, мог что-то неверно понять/прочитать - все мы люди. Буду очень рад читать конструктивную критику
Люди, утверждающие, что МТ не имеет ничего общего с реальностью из-за каких-то исключений - встречный вопрос: вы знаете про ЯП Go/Rust? Вместо тяжёлых виртуальных таблиц прерываний они используют лёгкие и предсказуемые ветвления, с лёгкостью реализующие аналогичное поведение (можно сколько угодно спорить на тему эффективности, но к теме статьи это не относится)
Это наверно камешек в мой адрес? :-) Да, я знаю и про Go и про Rust, и знаю, что у них, как и всех языков программирования реального мира есть возможность прерывания выполнения программы в любой момент времени. Просто некоторые языки умеют обрабатывать подобные прерывания, а другие нет, но сути это не меняет, тогда как МТ принципиально не умеет обрабатывать прерывания или переключать контекст, так как она всегда строго последовательная.
Не сказал бы, что камешек) просто хочу дать понять, что прерывания - это некое дополнение. На самом деле, когда вы пишете "throw new Exception" или что-то подобное, вы пользуетесь виртуальными таблицами прерываний. Они реализованы программно. В теории, для МТ вы тоже можете их реализовать (умные люди доказали до нас, что МТ может исполнить любой алгоритм). Так что в теории ещё как может :) ведь что такое контекст? Это тоже некая абстракция. По сути таблица переходов реализует оператор goto, и этого вполне может быть достаточно
Обработка исключений в однопотоке тоже последовательная. В многопотоке - нет. Но и МТ может быть недетерминированная))
Вы сейчас путаете прерывания и исключения, а это разные концепции. Исключение в вашем пример, это по сути дела способ глобально перейти на типизированный обработчик, по сути глобальный goto на тип данных (исключения). Но он работает в одном потоке и это обычный однопоточный код реализуемый на МТ, тогда как в контексте же МТ важны аппаратные прерывания (или вытесняющая многозадачность), на которую одна МТ не способна.
Да, умные люди доказали что в она в теории может выполнять любой алгоритм, вот только при важном допущении о наличии бесконечной памяти и неограниченном времени на работу, тогда как в реальности это невозможно.
Чтобы ответить на вопрос о том, есть ли МОДЕЛЬ какого-либо процесса, предлагаю автору грамотно построить вопрос, ЧТО является моделью? Дать ей определение, прежде чем искать
Если уж рассуждать о "грамотности", то тогда сначала нужно дать определения "процесса", а потом уж рассуждать о его МОДЕЛИ. Так, наверное?
Отвечаю сам. Определение ПРОЦЕСС в теории программ начинается с определения вычислимой функции (см Котов В.Е. Введение в теорию схем программ). А процесс вычисления таких функции представлен алгоритмом. А алгоритм - абстрактной машиной, реализующей такой алгоритм. Машина Тьюринга задает алгоритм для вычисления соответствующей вычислимой функции.
Вот, надеюсь, грамотный ответ на вопрос ЧТО является моделью.Моделью программы и соответственно программного процесса.
Спасибо за уточнение. Соглашусь, вы дали более корректный ответ)
Автор утверждает, что МТ - модель последовательного выполнения алгоритма; также он утверждает, что для параллельного выполнения подобной модели не существует (опять же, если верно всё понял). Если принять за истину, что детерминированная МТ является моделью в первом случае, то может ли недетерминированная являться моделью во втором? Как считаете?
Вы опять неправильно поняли. Мы можем детерминированным образом перейти от любой МТ к ее параллельной версии. По сути МТ это уже автомат (ее управление). Используя алгебру автоматов, можно любой одиночный автомат разложить на множество параллельных автоматов по операции умножения. Вот и все. И, кстати, это тоже будет детерминированная система - сеть автоматов. Ни какого недетерминизма нет и в помине.
Используя алгебру автоматов, можно любой одиночный автомат разложить на множество параллельных автоматов по операции умножения. Вот и все. И, кстати, это тоже будет детерминированная система - сеть автоматов. Ни какого недетерминизма нет и в помине.
Это верно только для синхронизированной работе сети автоматов, но любая асинхронная операция (например ожидание ввода пользователя) приводит общее состояние подобной сети в недетерминированое состояние.
Совсем не так. Создание еще одного детерминированного автомата для ввода, скажем, символа на вход текущего автомата на не разрушает детерминированность текущего автомата. Причем даже если автомат ввода работает асинхронно текущему автомату. Но если Вы такой эстет и хотите сохранить детерминированность поведения системы тек.автомат+автомат ввода то синхронизируйте их работу в едином времени. Делов-то, как говорится ;)
Инь и ян программирования или alter ego многопоточности