Cтраница 4
Чтобы проиллюстрировать метод, предположим, что проектировщик может разрабатывать ЦП на основе одного из двух различных методов. Первый из них - классический; в этом случае каждая команда выполняется полностью, и лишь затем выбирается для выполнения следующая команда. Второй использует трубопроводный принцип, когда одновременно с выполнением одной команды обрабатывается следующая за ней. В качестве примера входной информации имитатора будет использована задача вычисления полинома. Надо заметить, правда, что на практике для исследования альтернативных решений используется большое количество разных задач. [46]
Этот алгоритм должен работать на всех возможных значениях своих входов, принадлежащих некоторому полю. Максимальное число сложений, вычитаний и умножений, выполняемых алгоритмом, где максимум берется по всем допустимым входам, называется арифметической сложностью этого алгоритма. Заметим, что одни полиномы л-й степени вычислить оказывается проще, чем другие. Например, на вычисление xnjr2 тратится порядка log п операций, тогда как интуитивно мы чувствуем, что на вычисление произвольного полинома n - и степени должно расходоваться линейное число операций. Поэтому алгоритм для вычисления значений, пригодный только для конкретного полинома, может работать много быстрее, чем алгоритм, применимый ко всем полиномам. [47]