The OpenNET Project / Index page

[ новости /+++ | форум | теги | ]



Вариант для распечатки  
Пред. тема | След. тема 
Форум Разговоры, обсуждение новостей
Режим отображения отдельной подветви беседы [ Отслеживать ]

Оглавление

Проект HPC выпустил распараллеливающий компилятор Par4All 1.4, opennews (??), 31-Май-12, (0) [смотреть все]

Сообщения [Сортировка по времени | RSS]


11. "Проект HPC выпустил распараллеливающий компилятор Par4All 1...."  +/
Сообщение от Eugeni Dodonov (ok), 31-Май-12, 18:47 
> Которое в очередной раз показывает что математически доказать корректность параллельно выполняющейся программы — невозможно.

За полиноминалиное время - да, невозможно (http://en.wikipedia.org/wiki/Multiprocessor_scheduling).

Ответить | Правка | Наверх | Cообщить модератору

15. "Проект HPC выпустил распараллеливающий компилятор Par4All 1...."  +/
Сообщение от Mna (??), 01-Июн-12, 00:56 
А какая связь между Multiprocessor *scheduling* ("Given a set J of jobs where job ji has length li and a number of processors mi, what is the minimum possible time required to schedule all jobs in J on m processors such that none overlap?")
и доказательством правильности выполнения параллельной программы? частный случай даже: "многопоточной" программы
Ответить | Правка | Наверх | Cообщить модератору

18. "Проект HPC выпустил распараллеливающий компилятор Par4All 1...."  +/
Сообщение от Eugeni Dodonov (ok), 01-Июн-12, 01:23 
> А какая связь между Multiprocessor *scheduling* ("Given a set J of jobs
> where job ji has length li and a number of processors
> mi, what is the minimum possible time required to schedule all
> jobs in J on m processors such that none overlap?")
> и доказательством правильности выполнения параллельной программы? частный случай даже:
> "многопоточной" программы

Ммм чтобы проверить правильность выполнения программы ее надо выполнить, либо формально проверить. Формальная верификация - это np-complete (http://dl.acm.org/citation.cfm?id=2150582, хотя кроме этой публикации еще должны быть, но я их особо не искал), а эффективное параллельное выполнение - это тоже NP-hard. Так что проверить, конечно, возможно, но не за полиноминальное время.

Ну и в общем, программу можно привести к виду булевых формул, что тоже np-complete (http://en.wikipedia.org/wiki/Boolean_satisfiability).

Хотя, возможно, что-то упустил, тогда признаю что не прав.

Ответить | Правка | Наверх | Cообщить модератору

23. "Проект HPC выпустил распараллеливающий компилятор Par4All 1...."  +/
Сообщение от pavlinux (ok), 01-Июн-12, 01:53 
> это тоже NP-hard.

NP-hard вроде имеет сложность O(N²), но где-то на просторах сети,
шастал математик из МГУ, который клялся, что задачу об оптимальной
упаковке свёл к логарифмической.

Ответить | Правка | Наверх | Cообщить модератору

Архив | Удалить

Рекомендовать для помещения в FAQ | Индекс форумов | Темы | Пред. тема | След. тема




Партнёры:
PostgresPro
Inferno Solutions
Hosting by Hoster.ru
Хостинг:

Закладки на сайте
Проследить за страницей
Created 1996-2024 by Maxim Chirkov
Добавить, Поддержать, Вебмастеру