Тестирование алгоритмов

Если перед тестировщиком поставлена задача тестирования модуля, который реали­ зует преобразование данных по определенному алгоритму, наиболее строгий подход предполагает разработку входных и ожидаемых результирующих данных, которые позволят испытать возможности, варианты выполнения и условия возникновения ошибок алгоритма. Например, если перед специалистом по тестированию стоит за­ дача проверки алгоритма быстрого преобразования Фурье, проверке должны под­ вергаться несколько свойств этого преобразования. Поскольку быстрое преобразо­ вание Фурье является линейным, тестировщик создает тестовый случай для проверки равенства T(a*f, + b*f₂) = a*T(f,) + b*T(f₂). Поскольку быстрое преобразование Фурье является обратимым, тестировщик может выполнить прямое преобразование от­ дельных частот в спектральную функцию, а затем подвергнуть эту спектральную функцию обратному преобразованию и убедиться в совпадении результата с исход­ ными отдельными частотами, т.е. в том, что T~'[T\f)]=f. На этом этапе тестировщик может прийти к выводу, что код реализует обратимое линейное преобразование, но вопрос о том, является ли алгоритм действительно преобразованием Фурье, остается

открытым. Специалисту по тестированию наверняка придется создать данные для фиксированной частоты, для которой спектральная функция имеет только одну не­ нулевую составляющую на выбранной частоте, и убедиться, что ее амплитуда имеет правильное значение. За этим тестовым случаем могут прогоняться случаи для сле­ дующей " чистой" частоты и так далее, пока не будут протестированы все частоты и амплитуды.

Однако этот строгий подход относится к категории динамического тестирования, которое представляет собой тему главы 10. Значительно больший объем тестирова­ ния этого алгоритма можно предпринять во время его разработки с одновременным использованием статического тестирования. При разработке требований упомяну­ тый алгоритм формулируется, например, так: " Пользователь должен располагать утилитой, которая будет выполнять быстрое преобразование Фурье для комплексных данных, длина которых составляет степень двух, вплоть до 2¹⁰ включительно". Эта формулировка понятна персоналу инженерной или физической лаборатории, но разработчик программного обеспечения может не обладать достаточной математи­ ческой подготовкой. Во время эскизного проектирования это требование должно быть разбито на более понятные части. Прежде всего, входные и выходные данные помещаются в два двумерных массива длиной я, имеющие тип COMPLEX и макси­ мальную длину 210 во флаг ошибки типа INTEGER и в переменную Nтипа INTEGER, значение которой лежит в интервале [2, 10]. Приведенная информация эскизного проекта определяет пользовательский интерфейс, который дает возможность подго­ товить прототип, или заглушку, для помещения ее в графический интерфейс пользо­ вателя на этапе эскизного проектирования до того, как будут получены необходимые разъяснения от персонала инженерной или физической лаборатории.

На этапе рабочего проектирования алгоритм быстрого преобразования Фурье должен быть тщательно проанализирован. Здесь же понадобиться выбрать либо его оригинальную версию, разработанную Кули (Cooley) и Туки (Tukey) в 1965 году [12], либо какую-нибудь другую модификацию из более новых. Потребуется принять ряд решений относительно порядка обработки. Например, нужно ли применять обрат­ ный порядок следования разрядов выходных данных перед завершением преобразо­ вания, или предварительно сортировать таблицу данных синусов и косинусов с ис­ пользованием алгоритма с обратным порядком следования разрядов, после чего со­ хранять данные в фиксированной области памяти с тем же обратным порядком сле­ дования разрядов. Необходимо также принять решения относительно требования к точности алгоритма. Это решение должно подкрепляться задокументированными ссылками на техническую литературу, которая обосновывает требования по тестиро­ ванию точности результирующего алгоритма преобразования. Кроме того, нужно определить и требования ко времени выполнения преобразования, чтобы можно было проанализировать, достаточно ли будет скалярного процессора, или же потре­ буется процессор, в архитектуре которого реализованы векторные инструкции и дру­ гие функции обработки массивов.

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

²⁰⁶ Часть II. Технологии быстрого тестирования и советы

формулированию требований, которые не могут быть выполнены. Подход к этому вопросу с использованием быстрого тестирования заключается в сосредоточении усилий на поиске компромиссных решений на этапе рабочего проектирования. Затем компромиссные решения могут использоваться в качестве средства предотвращения изменчивости требований - одной из основных причин повышения затрат в ходе разработки с традиционным каскадным жизненным циклом. Компромиссные реше­ ния - это форма оптимизации перед утверждением окончательного варианта проек­ та, которая предотвращает многократное выполнение дорогостоящих разработок и динамического тестирования для отброшенных проектов/реализаций. В большинст­ ве финансовых оценок Института технологий программного обеспечения (Software Engineering Institute, SEI) финансовые инспектора фиксируют многочисленные на­ рушения в области проектирования программного обеспечения. Мы называем это явление " выбоинами" процесса разработки - " ямами" на дороге, которые иногда мо­ гут повредить движущийся по ней проект. Быстрое тестирование - это искусство расстановки по всему жизненному циклу разработки специалистов по тестированию, которые обнаруживают и сообщают о недостатках, как только они появляются.

ПРИМЕР: АНАЛИЗ ОБЩЕЙ ОШИБКИ ОКРУГЛЕНИЯ (ГЭРИ КОББ)

Еще одна область применения статического тестирования, которая особенно характерна для сферы научного программирования, — это анализ общей ошибки округления. Для того чтобы убедить в необходимости выполнения этой формы тестирования, стоит лишь' сослаться на один реальный случай из личной практики. В начале семидесятых компания, в которой я работал, заключила с одним из клиентов контракт на перенос их программ­ ного обеспеч з скалярного компьютера в векторный. В части контракта, касающей ся приемки конечных продуктов, было оговорено следующее условие: на векторном. компьютере преобразованные программы будут выполняться в 256 раз быстрее и вьщавать те же шестнадцатеричные результаты, что и при выполнении на скалярном компьютере.

К моменту назначения меня на должность руководителя группы преобразования про­ граммного обеспечения, я выполнил оценку основных характеристик каждой из основе ных преобразуемых систем, как с точки зрения времени выполнения, так и в плане по-' лучения распечаток входных и выходных переменных при прогоне программ для данных, которые владельцы приложений считали типовыми. Мне казалось, что это должно было помочь выполнить условия получения приемлемой производительности для выбранного, метода преобразования. Вскоре после начала преобразования программного обеспече­ ния один из моих сотрудников пришел к шутливому выводу: одно из выходных шестна-дцатеричных значении было названо W W M, что означало " worldwide mass" (" масса земного шара). Это значение было результатом суммирования масс всех ячеек сетки' наброшенной на весь земной шар. После совместной работы мы установили, что такое вычисление приводило к переполнению значения с плавающей точкой при обходе пои-мерно половины земного шара, поскольку накапливаемая сумма становилась настолько: большой, что добавление массы остальных ячеек сети не вело к изменению суммы Бо-лее того, скалярный компьютер выполнял 36-разрядные операции с плавающей точкой то время как векторный компьютер мог выполнять 32- или 64-разрядные векторные операции с плавающей точкой. Мы явно оказались в проигрышной позиции. Если выпоп-нять сложение с одинарной точностью, переполнение возникло бы прежде, чем удалось добраться даже до середины сетки (т.е. шестнадцатеричный результат отличается от

получаемого на скалярном компьютере). Если же выполнять суммирование с двойной' точностью, вычисление выполнялось бы медленнее (невозможно было получить 256-кратное увеличение производительности), и переполнение начинало бы возникать при обходе примерно 3/4 сетки (шестнадцатеричный результат отличается от первоначаль-

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

Приложение анализа общей ошибки округления суть технология статического тестирова-ния, берущая свое начало из области численного анализа, который подробно преподает-ся на университетских курсах по теории вычислительных машин и систем. 8 этой теории каждая переменная входных данных имеет связанный с ней вектор ошибок. Если Х, =С, +с„ a y, —D, +d„ то ошибка E определяется следующим выражением:

' где E(N)=SUM(c, + d,) для i=1 N

Далее, поскольку при считывании входных значений компьютер всегда усекает действи-тельные значения X, и У„ значения с, и d, всегда будут неотрицательными усеченными значениями. Следовательно, функция ошибок E(N) монотонно возрастает и является не-ограниченной сверху. Этот численный анализ может быть выполнен применительно к бо-лее сложным алгоритмам для проверки их ограничений по стабильности.

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