Заспорили с научруком. Кто-нибудь знает как называется фланг научных направлений, посвященный предсказанию времени работы программы? Допустим известно что некая (откомпилированная) программа работает 100 секунд на одном компьютере. Можно ли предсказать сколько эта же самая программа будет работать на другом компьютере? Пусть это будет даже в самых упрощенных условиях, например процессор — одноядерный, программа — однопоточная, винчестер и внешние медленные устройства не использует. Можно ли предсказать время ее работы на другом процессоре, пусть приблизительно, но с разумной погрешностью (100, 200, ну 300%)? Понятно что в общем случае предсказать ничего нельзя и из вредности всегда можно написать такую, которая из-за дополнительных 2 килобайт кеша на проце будет давать время работы на тридцать порядков быстрее, но все же кто-нибудь знает как называется направление таких работ и какие статьи почитать на эту тему прогнозирования — было бы круто.
Здравствуйте, PaulMinelly, Вы писали:
PM>Заспорили с научруком. Кто-нибудь знает как называется фланг научных направлений, посвященный предсказанию времени работы программы? Допустим известно что некая (откомпилированная) программа работает 100 секунд на одном компьютере.
Если известен алгоритм, точно известны данные и тем более, известно время работы в каком-то определённом аппаратном окружении, то расчёт времени работы тривиален. Если неизвестны данные — то используются граничные оценки для заданного алгоритма. Если алгоритм неизвестен, то и оценивать нечего.
ИМХО, как-то так. Научное направление тут не воткнёшь. Поправьте меня, если я не прав.
Я знаю только две бесконечные вещи — Вселенную и человеческую глупость, и я не совсем уверен насчёт Вселенной. (c) А. Эйнштейн
P.S.: Винодельческие провинции — это есть рулез!
Похоже, это не масштабируется даже для однотипных процессоров, работающих на разной частоте. Разве что пропорционально изменять все временные характеристики cpu, cash & ram.
Насчет научного направления не в курсе, но на более-менее популярном уровне можно порыться в окрестности бенчмарков и овеклокинга.
Здравствуйте, PaulMinelly, Вы писали:
PM>Заспорили с научруком. Кто-нибудь знает как называется фланг научных направлений, посвященный предсказанию времени работы программы? Допустим известно что некая (откомпилированная) программа работает 100 секунд на одном компьютере. Можно ли предсказать сколько эта же самая программа будет работать на другом компьютере? Пусть это будет даже в самых упрощенных условиях, например процессор — одноядерный, программа — однопоточная, винчестер и внешние медленные устройства не использует. Можно ли предсказать время ее работы на другом процессоре, пусть приблизительно, но с разумной погрешностью (100, 200, ну 300%)? Понятно что в общем случае предсказать ничего нельзя и из вредности всегда можно написать такую, которая из-за дополнительных 2 килобайт кеша на проце будет давать время работы на тридцать порядков быстрее, но все же кто-нибудь знает как называется направление таких работ и какие статьи почитать на эту тему прогнозирования — было бы круто.
Это, наверное, не в чистом виде, что тебе нужно, но посмотри работы отца и сына Воеводиных на http://parallel.ru/
Курица — это инструмент, с помощью которого одно яйцо производит другие.
Здравствуйте, PaulMinelly, Вы писали:
PM>Заспорили с научруком. Кто-нибудь знает как называется фланг научных направлений, посвященный предсказанию времени работы программы?
Астрология?
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
(пример)
Вот тут используют более сложный предиктор (предсказывает время выполнения на кластере) на практике, и он даже как-то работает: http://www.keldysh.ru/dvm/dvmhtm1107/rus/index.html
Возможно, там есть ссылки на исследования..
Здравствуйте, Геннадий Васильев, Вы писали:
ГВ>Здравствуйте, PaulMinelly, Вы писали:
PM>>Заспорили с научруком. Кто-нибудь знает как называется фланг научных направлений, посвященный предсказанию времени работы программы? Допустим известно что некая (откомпилированная) программа работает 100 секунд на одном компьютере.
ГВ>Если известен алгоритм, точно известны данные и тем более, известно время работы в каком-то определённом аппаратном окружении, то расчёт времени работы тривиален. Если неизвестны данные — то используются граничные оценки для заданного алгоритма. Если алгоритм неизвестен, то и оценивать нечего.
Подход бодрый, но у нас не изваестен алгоритм, у нас дана программа. Программный код, откомпилированный. В нем конечно есть какой-то алгоритм, но мы его не знаем, вернее он нам не интересен.
Еще конечно есть набор входных данных и известно время работы этой откомпилированной программы на каждом из набора входных данных. Вот такие условия.
Зная программу и время работы на каждом из входных данных на одном компьютере, можно предсказать как эта же программа будет работать с этими же входными данными но на другом компьютере (процессоре)?
Здравствуйте, D. Mon, Вы писали:
DM>(пример) DM>Вот тут используют более сложный предиктор (предсказывает время выполнения на кластере) на практике, и он даже как-то работает: DM>http://www.keldysh.ru/dvm/dvmhtm1107/rus/index.html DM>Возможно, там есть ссылки на исследования..
Вот это то что надо, но там задача нацелена на коммуникации между узлами кластера. Моя задача несколько проще: есть один узел, программа+входные данные, известно время ее работы на одном узле, надо предсказать время работы на другой архитектуре. Если кто еще знает ссылок на такую же тематику — было бы очень здорово!
Здравствуйте, PaulMinelly, Вы писали:
PM>Вот это то что надо, но там задача нацелена на коммуникации между узлами кластера. Моя задача несколько проще: есть один узел, программа+входные данные, известно время ее работы на одном узле, надо предсказать время работы на другой архитектуре. Если кто еще знает ссылок на такую же тематику — было бы очень здорово!
Слишком мало данных. Мало ли, что программа потратила T1 на одном компьютере. Вот мы добавили еще два гига памяти. А программа взяла и не использовала их!
Или взяла и использовала — совершенно невозможно в общем случае это понять.
То же самое касается многоядерности и всех других характеристик.
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, PaulMinelly, Вы писали:
ГВ>>Если известен алгоритм, точно известны данные и тем более, известно время работы в каком-то определённом аппаратном окружении, то расчёт времени работы тривиален. Если неизвестны данные — то используются граничные оценки для заданного алгоритма. Если алгоритм неизвестен, то и оценивать нечего.
PM>Подход бодрый, но у нас не изваестен алгоритм, у нас дана программа. Программный код, откомпилированный. В нем конечно есть какой-то алгоритм, но мы его не знаем, вернее он нам не интересен.
Свежо!
PM>Еще конечно есть набор входных данных и известно время работы этой откомпилированной программы на каждом из набора входных данных. Вот такие условия.
Бредовые условия. "У нас есть программа, но её алгоритм нам не интересен", зато интересна научная область, занимающаяся предсказанием времени работы неизвестно чего. По звёздам, что-ли?
PM>Зная программу и время работы на каждом из входных данных на одном компьютере, можно предсказать как эта же программа будет работать с этими же входными данными но на другом компьютере (процессоре)?
Нет, нельзя. Влиять может всё, что угодно: например, однопоточная программа не получит почти никаких бенефитов от многоядерного процессора, а программа, активно молотящая по диску определённо мало выиграет от простой замены процессора. И так далее, и тому подобное. Но если внутренности программы вам не интересны, то...
P.S.: Тебе для чего это нужно? Обосновать покупку новых компьютеров? Так подели одни мегагерцы на другие — будет достаточно.
Я знаю только две бесконечные вещи — Вселенную и человеческую глупость, и я не совсем уверен насчёт Вселенной. (c) А. Эйнштейн
P.S.: Винодельческие провинции — это есть рулез!
Здравствуйте, PaulMinelly, Вы писали:
PM>Вот это то что надо, но там задача нацелена на коммуникации между узлами кластера. Моя задача несколько проще: есть один узел, программа+входные данные, известно время ее работы на одном узле, надо предсказать время работы на другой архитектуре. Если кто еще знает ссылок на такую же тематику — было бы очень здорово!
Обрати внимание, там подсчитываются объективные характеристики работы программы (чем-то похоже на профилировщик). Иначе ты никакого прогноза сделать не сможешь.
Я знаю только две бесконечные вещи — Вселенную и человеческую глупость, и я не совсем уверен насчёт Вселенной. (c) А. Эйнштейн
P.S.: Винодельческие провинции — это есть рулез!
Здравствуйте, PaulMinelly, Вы писали:
PM>Заспорили с научруком. Кто-нибудь знает как называется фланг научных направлений, посвященный предсказанию времени работы программы? Допустим известно что некая (откомпилированная) программа работает 100 секунд на одном компьютере. Можно ли предсказать сколько эта же самая программа будет работать на другом компьютере? Пусть это будет даже в самых упрощенных условиях, например процессор — одноядерный, программа — однопоточная, винчестер и внешние медленные устройства не использует. Можно ли предсказать время ее работы на другом процессоре, пусть приблизительно, но с разумной погрешностью (100, 200, ну 300%)? Понятно что в общем случае предсказать ничего нельзя и из вредности всегда можно написать такую, которая из-за дополнительных 2 килобайт кеша на проце будет давать время работы на тридцать порядков быстрее, но все же кто-нибудь знает как называется направление таких работ и какие статьи почитать на эту тему прогнозирования — было бы круто.
Этими вопросами занимается теория алгоритмов. Конкретнее надо копать в сторону оценки вычислительной сложности алгоритмов.
PM>>Зная программу и время работы на каждом из входных данных на одном компьютере, можно предсказать как эта же программа будет работать с этими же входными данными но на другом компьютере (процессоре)?
ГВ>Влиять может всё, что угодно: например, однопоточная программа не получит почти никаких бенефитов от многоядерного процессора, а программа, активно молотящая по диску определённо мало выиграет от простой замены процессора. И так далее, и тому подобное. Но если внутренности программы вам не интересны, то...
Ты не торопись, я же для тебя специально написал что программа однопоточная, по диску она не молотит. Не молотит по диску (не использует внешних медленных устройств), только проц, память и кеши. Допустим кеши у процов одинаковые. Диск опять таки не используется. Время знаем, входные данные — тоже. Алгоритм одинаково работает на одних и тех же входных данных. Надо предсказать время с разумной погрешностью какой я написал выше в посте. Можно?
Здравствуйте, chukichuki, Вы писали:
C>Здравствуйте, PaulMinelly, Вы писали:
PM>>Заспорили с научруком. Кто-нибудь знает как называется фланг научных направлений, посвященный предсказанию времени работы программы? Допустим известно что некая (откомпилированная) программа работает 100 секунд на одном компьютере. Можно ли предсказать сколько эта же самая программа будет работать на другом компьютере? Пусть это будет даже в самых упрощенных условиях, например процессор — одноядерный, программа — однопоточная, винчестер и внешние медленные устройства не использует. Можно ли предсказать время ее работы на другом процессоре, пусть приблизительно, но с разумной погрешностью (100, 200, ну 300%)? Понятно что в общем случае предсказать ничего нельзя и из вредности всегда можно написать такую, которая из-за дополнительных 2 килобайт кеша на проце будет давать время работы на тридцать порядков быстрее, но все же кто-нибудь знает как называется направление таких работ и какие статьи почитать на эту тему прогнозирования — было бы круто.
C>Этими вопросами занимается теория алгоритмов. Конкретнее надо копать в сторону оценки вычислительной сложности алгоритмов.
Алгоритма-то нет. Есть откомпилированная программа и время ее работы на входных данных известно. Сколько она будет работать на тех же данных на другом проце. Вот такая постановка тут.
Здравствуйте, PaulMinelly, Вы писали:
C>>Этими вопросами занимается теория алгоритмов. Конкретнее надо копать в сторону оценки вычислительной сложности алгоритмов.
PM>Алгоритма-то нет. Есть откомпилированная программа и время ее работы на входных данных известно. Сколько она будет работать на тех же данных на другом проце. Вот такая постановка тут.
А откомпилированная программа алгоритм в себе не содержит ? Другое дело, если нету и откомпилированной программы, а есть только данные о том сколько времени она выполнялась на таком-то процессоре, на таких-то исходных данных. В принципе, основываясь на статистических данных (на каких-нибудь тестах производительности процессоров), можно приблизительно предсказать сколько она будет выполняться на тех же исходных данных на другом процессоре. Разумеется всякий изврат, типа оптимизации под конкретную архитектуру так не учтешь.
Здравствуйте, chukichuki, Вы писали:
C>Здравствуйте, PaulMinelly, Вы писали:
C>>>Этими вопросами занимается теория алгоритмов. Конкретнее надо копать в сторону оценки вычислительной сложности алгоритмов.
PM>>Алгоритма-то нет. Есть откомпилированная программа и время ее работы на входных данных известно. Сколько она будет работать на тех же данных на другом проце. Вот такая постановка тут.
C>А откомпилированная программа алгоритм в себе не содержит ?
Речь не об этом, речь о том что программа уже откомпилирована — какой в ней алогоритм — не разберешь. И рост этого алгоритма не интересен, по одной простой причине. Количество входных данных ограничено и на каждый из этих данных уже известно время работы этой программы на процессоре. Все. Рост тут не нужен и сложность алгоритма тоже, потому что у нас нет N неизвестной. У нас весь набор данных — фиксирован и время на каждом из экземпляре данных уже известно. (если и могут быть другие данные — то они нам не интересны ну или путь будут не интересны иначе задача совсем сложная).
C>Другое дело, если нету и откомпилированной программы, а есть только данные о том сколько времени она выполнялась на таком-то процессоре, на таких-то исходных данных.
Сейчас по понятнее опишу, может не понятно сказал что программа у нас откомпилированная уже. Так вот. У нас программа откомпилированная есть. По всем набору фиксированных входных данных известно время ее работы. Надо определить сколько она будет работать на другом компе. Вот такой сказ. C> В принципе, основываясь на статистических данных (на каких-нибудь тестах производительности процессоров), можно приблизительно предсказать сколько она будет выполняться на тех же исходных данных на другом процессоре. Разумеется всякий изврат, типа оптимизации под конкретную архитектуру так не учтешь.
Здравствуйте, PaulMinelly, Вы писали:
PM>Ты не торопись, я же для тебя специально написал что программа однопоточная, по диску она не молотит. Не молотит по диску (не использует внешних медленных устройств), только проц, память и кеши. Допустим кеши у процов одинаковые. Диск опять таки не используется. Время знаем, входные данные — тоже. Алгоритм одинаково работает на одних и тех же входных данных.
Ну это несколько меняет дело. То есть что-то вы про алгоритм всё же знаете.
PM>Надо предсказать время с разумной погрешностью какой я написал выше в посте. Можно?
В данном случае я бы просто поделил одни мегагерцы на другие, чтобы прикинуть примерный выигрыш. Какие на какие делить, думаю, понятно — если программа однопоточная, а процессор многоядерный, то нужно брать частоту одного ядра. Ещё имеет смысл почитать документацию производителя процессора, обратить внимание на настройки периферии на материнской плате (частоты шин процессора, памяти, кэшей и т.п.)
Как-то так.
Я знаю только две бесконечные вещи — Вселенную и человеческую глупость, и я не совсем уверен насчёт Вселенной. (c) А. Эйнштейн
P.S.: Винодельческие провинции — это есть рулез!
Здравствуйте, PaulMinelly, Вы писали:
PM>Зная программу и время работы на каждом из входных данных на одном компьютере, можно предсказать как эта же программа будет работать с этими же входными данными но на другом компьютере (процессоре)?
Можно. Время увеличится пропорционально разнице результатов известных тестов на этих процессорах. Скажем, на embedded процах популярен простой тест dmips, а на взрослых — SPEC .
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
кто-нибудь знает как называется направление таких работ и какие статьи почитать на эту тему прогнозирования — было бы круто.
Поправьте меня, если я не прав.
