Определение ресурсоёмкости алгоритма
Доброго времени суток!
Помогите, пожалуйста, со следующей задачей.
Есть описание алгоритма - объем и характер входных данных, их обработка и действия над результатами. Предполагается, что работа будет происходить в режиме реального времени, то есть указанные входные данных получаются с определенной периодичностью. Необходимо оценить требования к аппаратному обеспечения (тактовая частота, объем доступной памяти) реализованной согласно данному алгоритму программой (хотя бы в каких-то пределах). Программа будет работать на микроконтроллере, при чем никакой привязки к определенным семействам или моделям нет. Понимаю, что формулировка достаточно расплывчата, но буду благодарен за любые советы, ссылки на литературу... В общем, за любую информацию. Заранее спасибо!
Помогите, пожалуйста, со следующей задачей.
Есть описание алгоритма - объем и характер входных данных, их обработка и действия над результатами. Предполагается, что работа будет происходить в режиме реального времени, то есть указанные входные данных получаются с определенной периодичностью. Необходимо оценить требования к аппаратному обеспечения (тактовая частота, объем доступной памяти) реализованной согласно данному алгоритму программой (хотя бы в каких-то пределах). Программа будет работать на микроконтроллере, при чем никакой привязки к определенным семействам или моделям нет. Понимаю, что формулировка достаточно расплывчата, но буду благодарен за любые советы, ссылки на литературу... В общем, за любую информацию. Заранее спасибо!
Существуют два метода решения задачи вычисления ресурсоемкости
реализации алгоритма:
1. Метод эмпирических оценок, в котором необходимые исследования проводятся
путем вычисления процессорного времени выполнения реализации алгоритма на
компьютере с определенными характеристиками апаратных ресурсов процессора,
памяти, и т.п. В ходе исследований реализацию алгоритма запускают на нескольких
компьютерах с разными апаратными ресурсами, определяя, при этом, суммарное
процессорное время выполнения на каждом из них. Эти данные потом заносят в
таблицу с полями: номер, тактовая частота процессора, кол-во ядер,
объем оперативной памяти, операционная система (однозадачная/многозадачная среда),
суммарное время выполнения реализации алгоритма на заданном апаратном обеспечении.
Далее можно проводить разные исследования по нахождению усредненной оценки
производительности реализации алгоритма, или же минимизацию/масштабирование
затраченного процессорного времени/апаратных ресурсов, методом поиска экстремальных
значений. Код для оценки затраченного процессорного времени см. ниже:
2. Метод математического анализа, позволяющий путем поиска величины кол-ва, выполняемых
реализацией алгоритма, операций, оценить его производительность и промасштабировать
эту величину для разных апаратных ресурсов, зная при этом величину времени выполнения
одной операции на ПК с теми или иными апаратными ресурсами. Этот метод достаточно
сложный и я не могу его детально здесь описать. Этот метод детально описан в книге
Р. Седжвика "Фундаментальные алгоритмы на С++" том. 1. ВСЕ!!!
реализации алгоритма:
1. Метод эмпирических оценок, в котором необходимые исследования проводятся
путем вычисления процессорного времени выполнения реализации алгоритма на
компьютере с определенными характеристиками апаратных ресурсов процессора,
памяти, и т.п. В ходе исследований реализацию алгоритма запускают на нескольких
компьютерах с разными апаратными ресурсами, определяя, при этом, суммарное
процессорное время выполнения на каждом из них. Эти данные потом заносят в
таблицу с полями: номер, тактовая частота процессора, кол-во ядер,
объем оперативной памяти, операционная система (однозадачная/многозадачная среда),
суммарное время выполнения реализации алгоритма на заданном апаратном обеспечении.
Далее можно проводить разные исследования по нахождению усредненной оценки
производительности реализации алгоритма, или же минимизацию/масштабирование
затраченного процессорного времени/апаратных ресурсов, методом поиска экстремальных
значений. Код для оценки затраченного процессорного времени см. ниже:
Код:
time_t start,finish; double diff;
time (&start);
.............................
time (&finish);
diff = difftime (finish,start);
printf("time = %4.2f\n",diff);
time (&start);
.............................
time (&finish);
diff = difftime (finish,start);
printf("time = %4.2f\n",diff);
реализацией алгоритма, операций, оценить его производительность и промасштабировать
эту величину для разных апаратных ресурсов, зная при этом величину времени выполнения
одной операции на ПК с теми или иными апаратными ресурсами. Этот метод достаточно
сложный и я не могу его детально здесь описать. Этот метод детально описан в книге
Р. Седжвика "Фундаментальные алгоритмы на С++" том. 1. ВСЕ!!!
По второму пункту ищите еще "оценка сложности алгоритма". У Кнута этот вопрос подробно разжеван в "искуство программирования".
Спасибо, книга Седжвика и приведенные в ней ссылки очень помогли и продолжают помогать )