Comments 8
Не понял, чем ваша задача отличается от классической задачи регрессии? Если нет — то и решать нужно алгоритмами регрессионного анализа Link
Попробую пояснить: пользователя, приславшего исходные данные на решение, не может не интересовать сколько времени ждать результат. Пользователей несколько, а значит вычислительный ресурс делится между их задачами. Задачи приходят в неизвестные заранее моменты времени и с неизвестными размерностями, а последнее, согласно постановке задачи, определяюще влияет на время их выполнения. Иными словами, мы не можем просто запустить задачу пользователя, выдать ему некоторое предполагаемое время выполнения T и успокоиться, т.к. пока идет процесс выполнения его задачи, могут поступать/завершаться другие задачи => система может сильнее нагружается/разгружается, причем как именно — вопрос. Поэтому, имеет смысл уведомлять пользователя при изменении вычислительного ресурса, выделяемого на его задачу, и как это влияет на оставшееся время его ожидания результатов.
В такой постановке, если и возможно применение регрессивного анализа, то не слишком понятно как именно. Во всяком случае, выявление зависимостей поступления задач и их размерностей не выглядит перспективно — человек так непредсказуем... Надеюсь, мне удалось указать ключевые отличия задачи. Спасибо за комментарий!
В такой постановке, если и возможно применение регрессивного анализа, то не слишком понятно как именно. Во всяком случае, выявление зависимостей поступления задач и их размерностей не выглядит перспективно — человек так непредсказуем... Надеюсь, мне удалось указать ключевые отличия задачи. Спасибо за комментарий!
Собственно я говорил про построения функции зависимости времени выполнения одной задачи от размерности N (кстати, как она выглядит, было б интересно посмотреть).
Спасибо, добавил в статью пару графиков получившейся зависимости (соответствует сложности алгоритма решения задач). Про построение полинома Лагранжа можно посмотреть здесь, а ссылка на рабочий алгоритм содержится в тексте статьи.
Интересно. Я делал похожую штуку в системе, хранящей очередь разнотипных заданий в БД, выбираемых процессом-диспетчером на выполнение по N штук, где N — количество свободных процессов-обработчиков на момент вызова диспетчера.
Так как время выборки заданий было конечно и сравнимо с временем их выполнения, процесс-диспетчер вел статистику а) среднего времени выборки пачки заданий из БД, как функцию от M (размера пачки) и б) среднего времени выполнения заданий как функцию от типа задания и количества работающих процессов-обработчиков.
В итоге, алгоритм диспетчера был построен так, что он при свободных на текущий момент N процессах выбирал M заданий (M >= N), рассчитывая M с учетом времени выборки таким образом, что к моменту, когда выбранные из БД задания будут готовы к выполнению на процессах, какая-то часть процессов статистически завершится, и число свободных процессов будет >= M.
Так как время выборки заданий было конечно и сравнимо с временем их выполнения, процесс-диспетчер вел статистику а) среднего времени выборки пачки заданий из БД, как функцию от M (размера пачки) и б) среднего времени выполнения заданий как функцию от типа задания и количества работающих процессов-обработчиков.
В итоге, алгоритм диспетчера был построен так, что он при свободных на текущий момент N процессах выбирал M заданий (M >= N), рассчитывая M с учетом времени выборки таким образом, что к моменту, когда выбранные из БД задания будут готовы к выполнению на процессах, какая-то часть процессов статистически завершится, и число свободных процессов будет >= M.
Да, действительно, здесь налицо специфика, связанная со скоротечностью выполнения заданий.
В моей системе пока предполагаются типовые процессы, но понятно, что завести в БД поле «тип задания» и слегка переписать алгоритм не составляет труда. А вообще понравилась идея завести процессы-обработчики, мне видится это хорошим вариантом, когда речь идет о масштабируемой вычислительной системе. Добавил компьютер в сеть => добавил точку доступа в список.
Правда тут уже некая двухуровневая модель получается, надо будет еще поразмыслить на эту тему. В конце концов дешевле и надежнее расширять сеть горизонтально, а не менять «железо» всякий раз, когда клиенты затолкают друг-друга локтями донельзя)).
Кстати, по какому протоколу взаимодействие осуществлялось?
В моей системе пока предполагаются типовые процессы, но понятно, что завести в БД поле «тип задания» и слегка переписать алгоритм не составляет труда. А вообще понравилась идея завести процессы-обработчики, мне видится это хорошим вариантом, когда речь идет о масштабируемой вычислительной системе. Добавил компьютер в сеть => добавил точку доступа в список.
Правда тут уже некая двухуровневая модель получается, надо будет еще поразмыслить на эту тему. В конце концов дешевле и надежнее расширять сеть горизонтально, а не менять «железо» всякий раз, когда клиенты затолкают друг-друга локтями донельзя)).
Кстати, по какому протоколу взаимодействие осуществлялось?
Архитектура была такая — очередь заданий находилась на единственном сервере БД, к которому могло ходить от 1 до K серверов приложений, кладущих задания в очередь, либо забирающих их оттуда (через обычную сетевую SQL-коннекцию).
На каждом сервере приложения крутился 1 диспетчерский процесс и пул процессов-обработчиков. Диспетчерский процесс был придуман для того, чтобы обработчики сами в БД за заданиями не ходили, т.к. из БД выгодно забирать задания пачками.
В общем случае, некая единица работы могла содержать несколько фаз, каждая из которых представляла собой задание в очереди. В зависимости от типа задания метаданными накладывались правила, например такие, что некоторые типы были хостонезависимыми, а некоторые — требовали, чтобы задание выполнялось на том же хосте, что и хост, добавивший задание в очередь.
Кроме того, в самих метаданных задания в БД была возможность создавать начало (fork) и конец (collect) параллельных цепочек — ее логика поддерживалась внутри самой БД сторед-процедурами, которые клали, выбирали и отмечали как выполненные задания из базы.
Использовалось все это в системе распознавания изображений (конкретно типа еды по ее фотографии) — например, типичная работа содержала такую последовательность — препроцессинг -> выборка контекстов распознавания -> запихивание контекстов в очередь (точка fork) со ссылкой вперед на задание типа collect (оно делало aggregate_context_results) -> debug_out (опционально) -> save.
На каждом сервере приложения крутился 1 диспетчерский процесс и пул процессов-обработчиков. Диспетчерский процесс был придуман для того, чтобы обработчики сами в БД за заданиями не ходили, т.к. из БД выгодно забирать задания пачками.
В общем случае, некая единица работы могла содержать несколько фаз, каждая из которых представляла собой задание в очереди. В зависимости от типа задания метаданными накладывались правила, например такие, что некоторые типы были хостонезависимыми, а некоторые — требовали, чтобы задание выполнялось на том же хосте, что и хост, добавивший задание в очередь.
Кроме того, в самих метаданных задания в БД была возможность создавать начало (fork) и конец (collect) параллельных цепочек — ее логика поддерживалась внутри самой БД сторед-процедурами, которые клали, выбирали и отмечали как выполненные задания из базы.
Использовалось все это в системе распознавания изображений (конкретно типа еды по ее фотографии) — например, типичная работа содержала такую последовательность — препроцессинг -> выборка контекстов распознавания -> запихивание контекстов в очередь (точка fork) со ссылкой вперед на задание типа collect (оно делало aggregate_context_results) -> debug_out (опционально) -> save.
Читаю и ясно вижу — ну так и просится здесь что-то вроде сервисной шины (скажем mule esb, open esb или что-нибудь эдакое от oracle). Большинство вопросов, которые перекрывала избыточная информация в Вашей БД, как раз и реализовано в сервисных шинах. И, по идее, шина призвана выравнивать нагрузку, распихивать задачи и все такое, чтобы лишний раз не грузить сервер БД… но в Вашем случае, когда речь идет о скоротечности и массовости вычислений, не берусь утверждать, что за удобство и масштабируемость не придется платить производительностью.
А вообще — весьма занятно, не смотря на то, что мы бесконечно отдалились от темы статьи. Спасибо!
А вообще — весьма занятно, не смотря на то, что мы бесконечно отдалились от темы статьи. Спасибо!
Sign up to leave a comment.
Прогноз времени выполнения типовых последовательных «тяжелых» вычислений в многопроцессорной системе в условиях непрогнозируемого поступления заявок