Курсовая по информатике и вычислительной технике: как связать алгоритм, программную реализацию и ресурсы вычислительной системы

Курсовая по информатике и вычислительной технике может быть посвящена программному алгоритму, вычислительной системе, микропроцессору, сетевому узлу или их сочетанию. Чтобы работа не распалась на обзор железа и отдельный кусок кода, нужен единый вычислительный вопрос: что обрабатывается, каким алгоритмом и на каких ресурсах.

Сильная работа показывает не только, что программа выдаёт правильный ответ, но и сколько ресурсов она требует и почему выбран именно такой способ реализации.

Формализуйте задачу

До кода определите:

• вход;
• выход;
• ограничения;
• размер;
• критерий правильности.

Например, задача сортировки - это не «упорядочить данные», а обработать массив заданного типа с определённым объёмом и требованиями.

Формализация помогает выбирать алгоритм.

Базовое решение

Сначала полезно иметь простую версию.

Она может быть медленной, но понятной.

Базовый алгоритм нужен для:

• проверки результата;
• сравнения;
• оценки ускорения.

Не оптимизируйте код до того, как убедились, что он правильно решает задачу.

Асимптотика

Оцените время и память.

Но Big O не заменяет эксперимент.

Два алгоритма O(n log n) могут сильно различаться по константам, памяти и поведению кэша.

Используйте теорию как верхний уровень анализа.

Структура данных

Выбор структуры влияет на алгоритм.

Сравните, что важнее:

• быстрый поиск;
• вставка;
• последовательный обход;
• память.

Не используйте связный список там, где основная операция - случайный доступ по индексу, только потому, что он изучался на курсе.

Память

Покажите:

• объём входа;
• дополнительные структуры;
• стек;
• буферы.

Для больших данных память может стать ограничением раньше времени выполнения.

Не держите несколько полных копий массива без необходимости.

Процессор

Если работа связана с производительностью, учитывайте архитектурные факторы:

• кэш;
• ядра;
• векторные инструкции;
• частоту;
• память.

Не объясняйте ускорение только частотой процессора.

Современная производительность зависит от многих уровней.

Кэш

Последовательный доступ к памяти часто быстрее хаотичного.

Два алгоритма с похожим числом операций могут различаться по кэш-локальности.

Если тема позволяет, проведите эксперимент с разным расположением данных.

Параллелизм

До многопоточности определите, какая часть задачи независима.

Разделите:

• последовательную часть;
• параллельную;
• синхронизацию.

Не ожидайте линейного ускорения на N ядрах.

Есть накладные расходы и непараллельный участок.

Гонка данных

Если несколько потоков меняют общую память, результат может зависеть от порядка выполнения.

Не исправляйте проблему задержками sleep.

Используйте корректную синхронизацию или переработайте обмен данными.

Блокировка

Она обеспечивает корректность, но может уменьшать параллелизм.

Измерьте время ожидания, если оно существенно.

Иногда локальные буферы и последующее объединение лучше одной глобальной блокировки.

GPU

Графический ускоритель полезен для массового параллелизма.

Но передача данных между CPU и GPU тоже стоит времени.

Для маленькой задачи запуск ядра может быть медленнее обычного CPU-кода.

Сравнивайте полный цикл.

Ввод-вывод

Программа может быть ограничена диском или сетью, а не вычислениями.

Измерьте отдельно:

• чтение;
• обработку;
• запись.

Не оптимизируйте алгоритм, если 90% времени уходит на загрузку данных.

Файловый формат

Для больших данных текстовый формат удобен человеку, но может быть медленным и объёмным.

Сравните при необходимости:

• CSV;
• бинарный;
• сериализацию.

Но учитывайте переносимость и простоту.

Архитектура компьютера

Если тема аппаратная, покажите путь команды и данных:

• память;
• процессор;
• регистры;
• шина;
• устройства.

Не переписывайте характеристики конкретного CPU без связи с задачей.

Микроконтроллер

Для встроенной системы важны ограничения:

• RAM;
• Flash;
• частота;
• периферия;
• энергопотребление.

Код, который нормально работает на ПК, может не помещаться в микроконтроллер.

Покажите бюджет ресурсов.

Прерывания

Если устройство реагирует на события, используйте их осмысленно.

Обработчик должен быть коротким.

Тяжёлую работу лучше переносить в основной цикл или задачу.

Не делайте длительную задержку внутри прерывания.

Таймер

Для периодического процесса аппаратный таймер даёт более стабильный период, чем программная задержка.

Если важна частота выборки, измерьте её фактически.

Не предполагайте идеальный период по строке delay.

Протокол обмена

Для связи между устройствами задайте:

• кадр;
• адрес;
• контроль;
• скорость;
• обработку ошибки.

Не передавайте числа без понятного формата.

Система должна отличать данные от повреждённого пакета.

Контроль ошибок

Можно использовать:

• checksum;
• CRC;
• повтор;
• подтверждение.

Выбор зависит от риска ошибки и требований.

Не усложняйте протокол, если среда надёжная и цена ошибки мала, но объясните решение.

Бенчмарк

Для сравнения алгоритмов используйте одинаковые условия:

• данные;
• компилятор;
• оптимизацию;
• устройство;
• число повторов.

Первый запуск иногда отличается из-за кэша или JIT.

Не делайте вывод по одному измерению.

Профилирование

Не оптимизируйте «на глаз».

Профилировщик показывает, где реально тратится время.

Если функция занимает 2% времени, ускорение её вдвое почти не изменит программу.

Правильность

Скорость не важна, если результат неверен.

Создайте тесты:

• обычный случай;
• пустой;
• минимальный;
• максимальный;
• случайные данные;
• граничные значения.

Воспроизводимость

Запишите версии:

• ОС;
• компилятора;
• библиотек;
• оборудование.

При сравнении производительности это критично.

Защита

Покажите:

1. задачу;
2. базовый алгоритм;
3. улучшение;
4. оценку сложности;
5. эксперимент;
6. ресурсы.

Курсовая по информатике и вычислительной технике выглядит профессионально тогда, когда программное решение рассматривается вместе с реальной вычислительной платформой и подтверждается измерениями, а не только листингом кода.