Исходное сообщение
"Проект HPC выпустил распараллеливающий компилятор Par4All 1...." Отправлено Eugeni Dodonov, 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). Хотя, возможно, что-то упустил, тогда признаю что не прав.

Ваше сообщение
Имя*:
EMail:	Для отправки ответов на email укажите знак ! перед адресом, например, !user@host.ru (!! - не показывать email). Более тонкая настройка отправки ответов производится в профиле зарегистрированного участника форума.
Заголовок*:
Сообщение*:
	Введите код, изображенный на картинке: