А.Ю. Попов
12
№ 2 не учитываются влияние параллельного выполнения кода мене-
джера памяти на разных ядрах и работа менеджера памяти до и после
кода эксперимента. Эксперимент на ЭВМ № 2 показал, что при за-
пуске программного эксперимента и ОС на одном ядре временная
сложность возрастает приблизительно в два раза.
Полный учет времени выделения и освобождения памяти выпол-
нен при программной реализации эксперимента на ЭВМ № 3, функ-
ционирующей в однозадачном режиме без разделения времени.
Для операции
Удаление
временная сложность аппаратного реше-
ния на основе СП в 11,8 раза ниже временной сложности программ-
ной реализации на многоядерной платформе № 1, в 22,2 раза ниже
ЭВМ № 2 и в 164,4 раза ниже ЭВМ № 3. Временная сложность аппа-
ратного выполнения операции
Поиск
в 9,8 раза ниже временной
сложности программной реализации на ЭВМ № 1, в 15,3 раза ниже
ЭВМ № 2 и в 31,4 раза ниже ЭВМ № 3.
Для сравнения аппаратной сложности экспериментальных плат-
форм был использован отчет о задействованных в аппаратном про-
екте на ПЛИС FPGA Virtex II Pro ресурсах кристалла, использован-
ных при реализации СП (см. таблицу). Аппаратная сложность про-
екта
составила
840
тыс.
эквивалентных
вентилей.
Микропроцессоры, использованные в эксперименте, имеют следу-
ющую аппаратную сложность: ЭВМ № 1 Core i5 ~ 730 млн вентилей
(в 869 раз больше); ЭВМ № 2 Pentium 4 ~ 42 млн вентилей (в 50 раз
больше). Аппаратная сложность встраиваемой системы на основе
микропроцессорного ядра Microblaze (процессор, шина, контроллер
памяти) составляет около 40 тыс. эквивалентных вентилей, что в 21
раз меньше аппаратной сложности СП.
Сравнение временной и аппаратной сложностей
СП и микропрограммных ЭВМ
ЭВМ
Операция, такты
Аппаратная
сложность,
вентили
Добавление Удаление Поиск
На основе СП
A
*
B
*
C
*
D
**
№ 1 (Core i5, 4 Гб RAM)
3,2·A
11,8·B
9,8·C
869·D
№ 2 (Pentium 4, 256 Мб RAM)
5,7·A
22,2·B 15,3·C
42·D
№ 3 (Microblaze, 256 Мб RAM)
42,7·A
164,4·B 31,4·C
D/21
* А, В, С — усл. ед. измерения временной сложности такта.
* D — усл. ед. измерения аппаратной сложности, вентили.
