chepelash / fpga_lab_b3 Goto Github PK

Пузырьковая сортировка

Модуль сортировки на ПЛИС.

Параметры модуля:

• DWIDTH - ширина слов;
• AWIDTH - ширина адреса памяти.

Входы модуля:

• clk_i - тактовый сигнал;
• srst_i - синхронный сброс;
• data_i - входные данные;
• sop_i - начало транзакции;
• eop_i - конец транзакции;
• val_i - сигнал валидности data_i, sop_i, eop_i.

Выходы модуля:

• data_o - выходные данные;
• sop_o - начало транзакции;
• eop_o - конец транзакции;
• val_o - сигнал валидности data_o, sop_o, eop_o;
• busy_o - сигнал статуса.

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

На вход данные поступают по последовательному интерфейсу, состоящему из 4-х сигналов:

• data_i - входные данные;
• sop_i - начало транзакции;
• eop_i - конец транзакции;
• val_i - сигнал валидности data_i, sop_i, eop_i.

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

Выходной интерфейс содержит сигналы:

• data_o - выходные данные;
• sop_o - начало транзакции;
• eop_o - конец транзакции;
• val_o - сигнал валидности data_o, sop_o, eop_o.

Модуль состоит из 3-х составляющих:

1. ram_memory.sv - обычный модуль памяти;
2. mem_cntr.sv - модуль контроля адреса записи для модуля памяти;
3. sorter.sv - модуль сортировки.

1 ram_memory.sv

Модуль памяти на 2^AWIDTH значений шириной DWIDTH.

• Входы:
  • data_i - входные данные, приходят извне;
  • rdpntr_i - адрес чтения, устанавливается модулем сотрировки sorter.sv;
  • wren_i - сигнал разрешения записи, приходит извне;
  • wrpntr_i - адрес записи, устанавливается модулем mem_cntr.sv.
• Выход:
  • q_o - выходные данные, поступают на модуль сортировки sorter.sv.

2 mem_cntr.sv

Задачи:

• Модуль устанавливает адрес записи для памяти ram_memory.sv, в который записываются входные данные.

• Выставляет флаг busy_o по окончанию входной посылки. Адрес записи - счетчик количества слов в памяти. Значения всегда записываются от 0 адреса до числа слов в текущей посылке. Счетчик отсчитывает количество тактов, когда сигнал val_i был в верхнем уровне. По приходу сигнала окончания посылки eop_i сигнал busy_o устанавливается в 1, который используется в модуле сортировки sorter.sv как сигнал начала своей работы. По приходу сигнала сброса от модуля сортировки clr_i Адрес записи и флаг busy_o устанавливаются в 0.

• Входы

  • clr_i - сигнал сброса адреса и сигнала busy_o;
  • eop_i - конец транзакции;
  • val_i - сигнал валидности data_i, sop_i, eop_i.

• Выходы

  • busy_o - сигнал статуса;
  • wraddr_o - адрес записи в память ram_memory.sv.

3 sorter.sv

Алгоритм сортировки - пузырьковая последовательная сортировка. Работа модуля состоит из 3-х этапов:

1. запись значений из памяти ram_memory.sv в регистры;
2. сама сортировка пузырьком;
3. отправка выходных данных.

1 Запись значений в регистры

Приход верхнего уровня сигнала wren_i означает конец приема входной посылки и запии ее в память. Сигнал cntr_i отображает количество записанных слов в памяти. Слова записаны в памяти с 0-го адреса, поэтому для считывания используется счетчик intr_cntr от 0 до ( cntr_i - 1 ). По окончанию записи для начала следующего этапа сигнал writing_done устанавливается в 1.

2 Сортировка

Алгоритм описан здесь. Для прохода по массиву данных используются регистры i_iterator и j_iterator. При достижении регистром i_iterator значения ( cntr_i - 1 ) сортировка завершается, сигнал sort_done устанавливается в 1 и начинается этап отправления отсортированных данных.

3 Отправка

Сигнал val_o устанавливается в 1. На основе счетчика intr_cntr, использовавшегося для чтения данных из памяти, формируются сигналы начала транзакции sop_o (при intr_cntr == cntr_i - 1) и конца транзакции eop_o (при intr_cntr == 0), счетчик используется как индекс для массива регистров отсортированных значений. По сигналу eop_o все внутренние флаги сбрасываются в 0 и регистры очищаются.

Ограничения:

Значения записываются в массив регистров, поэтому главное ограничение - максимальное количество значений, количество регистров (параметры 2^AWIDTH * DWIDTH). Количество тактов, наобходимых для сортировки входных значений, не фиксировано и зависит от количества входных значений. Сложность применяемого алгоритма стремится к О(n^2).

Тестирование модуля

Тестбенч находится тут tb\sorting_tb.sv. Для симуляции использовался ModelSim 10.5b, скрипт запуска находится тут tb\make.do. Запускать из командной строки vsim -do tb\make.do. В Тб есть 3 параметра DWIDTH, AWIDTH, ITER_NUM.

• DWIDTH - ширина слов;
• AWIDTH - ширина адреса памяти;
• ITER_NUM - количество проверок. Значение должно быть больше 0! При больших значениях DWIDTH и AWIDTH рекомендуется устанавливать значения поменьше из-за увеличения времени тестирования.

Тест генерирует необходимые сигналы валидности и случайную входную последовательность случайной длины от 3 до 2^AWIDTH, и при фиксированной величине 2^AWIDTH. Вместе с сигналами валидности сохраняется выходная последовательность из модуля. В процессе теста проверяются правильная установка выходных управляющих сигналов и правильная сортировка данных. Отдельно проверяется установка управляющих сигналов в 0 после сортировки и работа при "максимальной" нагрузке, когда на следующий такт после формирования сигналов завершения выходной посылки (eop_o == 1) на модуль оправляется следующая входная посылка для сортировки. По завершению теста успешно будет отображена надпись "Everything is OK!".