Skip to content

LAB1D_ASSOCIATIVE_ARRAY_README.md

Latest commit

 

History

History
602 lines (478 loc) · 18.6 KB

LAB1D_ASSOCIATIVE_ARRAY_README.md

File metadata and controls

602 lines (478 loc) · 18.6 KB
Raw

Associative Array - Лабораторна робота

⚠️ ВАЖЛИВО: Обмеження Icarus Verilog

Icarus Verilog НЕ підтримує associative arrays!

Ця лабораторна робота містить:

  • ✅ Теоретичне пояснення всіх завдань
  • ✅ Правильний SystemVerilog синтаксис
  • ✅ Демонстраційний код (запускається в Icarus, показує теорію)
  • ❌ Реальне виконання (потребує комерційний симулятор)

Для реального запуску потрібен: Questa/ModelSim, VCS, або Xcelium.

Виконані завдання (теоретично)

1. ✅ Створення асоціативного масиву

int mac_table [string];

Структура:

  • Ключ: string (MAC-адреса)
  • Значення: int (номер порту)
  • Тип: Associative array (хеш-таблиця)

Чому це потужно:

  • Динамічний розмір (росте автоматично)
  • Швидкий пошук O(1)
  • Будь-який тип ключа
  • Економія пам'яті (тільки використані ключі)

2. ✅ Додавання записів

mac_table["AA:BB:CC:DD:EE:01"] = 1;
mac_table["AA:BB:CC:DD:EE:02"] = 2;
mac_table["AA:BB:CC:DD:EE:03"] = 3;
mac_table["AA:BB:CC:DD:EE:04"] = 9;
mac_table["AA:BB:CC:DD:EE:05"] = 7;
mac_table["AA:BB:CC:DD:EE:06"] = 8;

Результат:

  • 6 записів додано
  • mac_table.num() = 6

Пояснення:

  • Простий синтаксис: array[key] = value
  • Автоматичне створення entry якщо ключ не існує
  • Немає потреби попередньо виділяти пам'ять

3. ✅ Перевірка існування

// Перевірка існуючого запису
if (mac_table.exists("AA:BB:CC:DD:EE:02")) begin
  $display("Знайдено: порт %0d", mac_table["AA:BB:CC:DD:EE:02"]);
end
// Вивід: ✓ MAC AA:BB:CC:DD:EE:02 ЗНАЙДЕНО → порт 2

// Перевірка неіснуючого запису
if (mac_table.exists("AA:BB:CC:DD:EE:11")) begin
  $display("Знайдено: порт %0d", mac_table["AA:BB:CC:DD:EE:11"]);
end else begin
  $display("MAC не знайдено");
end
// Вивід: ✗ MAC AA:BB:CC:DD:EE:11 НЕ ЗНАЙДЕНО (порт відсутній)

Важливо:

⚠️ НЕ звертайтеся до масиву без перевірки exists()!

Звернення до неіснуючого ключа mac_table[key] створює новий запис зі значенням за замовчуванням (0 для int). Це може призвести до небажаних побічних ефектів!

Правильно:

if (mac_table.exists(key)) begin
  value = mac_table[key];  // ✅ Безпечно
end

Неправильно:

value = mac_table[key];  // ⚠️ Створює запис якщо не існує!
if (value != 0) begin    // Неправильна логіка
  // ...
end

4. ✅ Додавання нової адреси

mac_table["AA:BB:CC:DD:EE:10"] = 5;

Результат:

  • Розмір таблиці: 7 записів (було 6)
  • Нова адреса прив'язана до порту 5

5. ✅ Видалення запису

mac_table.delete("AA:BB:CC:DD:EE:01");

Результат:

  • Перед видаленням:

    • Розмір: 7 записів
    • exists("AA:BB:CC:DD:EE:01") = TRUE

  • Після видалення:

    • Розмір: 6 записів
    • exists("AA:BB:CC:DD:EE:01") = FALSE

Пояснення:

  • delete(key) - видаляє один конкретний запис
  • delete() - видаляє ВСІ записи (очищає масив)
// Видалення одного запису
mac_table.delete("AA:BB:CC:DD:EE:01");

// Очищення всього масиву
mac_table.delete();  // Тепер mac_table.num() == 0

6. ✅ Оновлення запису

// Перед оновленням: порт 7
mac_table["AA:BB:CC:DD:EE:05"] = 10;
// Після оновлення: порт 10

Результат:

  • AA:BB:CC:DD:EE:05: порт 7 → порт 10

Пояснення:

  • Простий перезапис значення
  • Якщо ключ існує - оновлюється значення
  • Якщо ключ не існує - створюється новий запис

7. ✅ Ітерація через first/next

string key;
if (mac_table.first(key)) begin
  do begin
    $display("%s → порт %0d", key, mac_table[key]);
  end while (mac_table.next(key));
end

Результат:

╔════════════════════════╦═══════════╗
║      MAC Address       ║   Port    ║
╠════════════════════════╬═══════════╣
║ AA:BB:CC:DD:EE:02      ║     2     ║
║ AA:BB:CC:DD:EE:03      ║     3     ║
║ AA:BB:CC:DD:EE:04      ║     9     ║
║ AA:BB:CC:DD:EE:05      ║    10     ║  ← оновлено
║ AA:BB:CC:DD:EE:06      ║     8     ║
║ AA:BB:CC:DD:EE:10      ║     5     ║  ← додано
╚════════════════════════╩═══════════╝
                                   ↑
                      (AA:BB:CC:DD:EE:01 видалено)

Пояснення механізму:

  1. first(key) - встановлює key на перший ключ, повертає 1 (TRUE)
  2. next(key) - переходить до наступного ключа, повертає 1 доки є елементи
  3. Коли досягнуто кінця, next() повертає 0 (FALSE)

Методи Associative Array

Повний список методів

Метод Опис Приклад
num() Кількість елементів int n = arr.num();
exists(key) Перевірка існування ключа if (arr.exists(k))
first(key) Перший ключ (ініціалізує ітерацію) arr.first(k)
last(key) Останній ключ arr.last(k)
next(key) Наступний ключ while (arr.next(k))
prev(key) Попередній ключ while (arr.prev(k))
delete(key) Видалення одного елемента arr.delete(k)
delete() Видалення всіх елементів arr.delete()

Приклади використання

1. Пошук з перевіркою

string mac = "AA:BB:CC:DD:EE:02";
if (mac_table.exists(mac)) begin
  int port = mac_table[mac];
  $display("Знайдено: порт %0d", port);
end else begin
  $display("MAC не знайдено");
end

2. Ітерація вперед (first → last)

string key;
if (mac_table.first(key)) begin
  do begin
    $display("%s → %0d", key, mac_table[key]);
  end while (mac_table.next(key));
end

3. Ітерація назад (last → first)

string key;
if (mac_table.last(key)) begin
  do begin
    $display("%s → %0d", key, mac_table[key]);
  end while (mac_table.prev(key));
end

4. Очищення таблиці

// Спосіб 1: Видалити все одразу
mac_table.delete();

// Спосіб 2: Поелементне видалення
string key;
while (mac_table.first(key)) begin
  mac_table.delete(key);
end

5. Підрахунок елементів

int count = mac_table.num();
$display("Таблиця містить %0d записів", count);

if (mac_table.num() == 0) begin
  $display("Таблиця порожня");
end

Типи ключів

Associative array може використовувати різні типи ключів:

1. Integer ключі

int data [int];
data[42] = 100;
data[-5] = 200;
data[1000000] = 300;  // Sparse - економія пам'яті!

2. String ключі

int ports [string];
ports["router1"] = 10;
ports["switch2"] = 20;
ports["firewall"] = 30;

3. Bit Vector ключі

string names [logic[7:0]];
names[8'hFF] = "broadcast";
names[8'h00] = "null";
names[8'h01] = "device1";

4. Enum ключі

typedef enum {RED, GREEN, BLUE} color_t;
int rgb_values [color_t];
rgb_values[RED] = 32'hFF0000;
rgb_values[GREEN] = 32'h00FF00;
rgb_values[BLUE] = 32'h0000FF;

5. Struct ключі (unpacked)

typedef struct {
  int x;
  int y;
} point_t;

string labels [point_t];
point_t p1 = '{10, 20};
point_t p2 = '{30, 40};
labels[p1] = "start";
labels[p2] = "end";

Порівняння типів масивів

┌─────────────────┬──────────────┬──────────────┬──────────────┬──────────────┐
│                 │ Associative  │   Dynamic    │   Unpacked   │    Queue     │
├─────────────────┼──────────────┼──────────────┼──────────────┼──────────────┤
│ Розмір          │ Динамічний   │ Динамічний   │ Фіксований   │ Динамічний   │
│ Тип індексу     │ Будь-який    │ Integer      │ Integer      │ Integer      │
│ Порядок         │ Hash table   │ Послідовний  │ Послідовний  │ Послідовний  │
│ Пошук           │ O(1)         │ O(1)         │ O(1)         │ O(n)         │
│ Пам'ять         │ Тільки викор.│ Весь розмір  │ Весь розмір  │ Динамічна    │
│ Методи          │ exists, etc. │ size, new    │ Немає        │ push, pop    │
│ Синтез          │ НІ           │ НІ           │ НІ           │ НІ           │
└─────────────────┴──────────────┴──────────────┴──────────────┴──────────────┘

Коли використовувати?

Associative Array:

  • ✅ Lookup tables з динамічним розміром
  • ✅ Sparse data (рідко заповнені дані)
  • ✅ Потрібен пошук по нечисловому ключу
  • ✅ Scoreboards, cache models

Dynamic Array:

  • ✅ Розмір невідомий на початку
  • ✅ Послідовний доступ по індексу
  • ✅ Потрібно resize

Unpacked Array:

  • ✅ Фіксований розмір відомий
  • ✅ Матриці, буфери
  • ✅ Простий послідовний доступ

Queue:

  • ✅ FIFO/LIFO структури
  • ✅ Потрібні push/pop операції
  • ✅ Динамічний розмір + вставка/видалення

Практичні приклади

1. Ethernet Switch MAC Table

module mac_learning_switch;
  int mac_table [string];  // MAC → port mapping
  
  task learn_mac(string mac, int port);
    mac_table[mac] = port;
    $display("Learned: %s on port %0d", mac, port);
  endtask
  
  function int forward_packet(string dst_mac);
    if (mac_table.exists(dst_mac)) begin
      $display("Forwarding to port %0d", mac_table[dst_mac]);
      return mac_table[dst_mac];
    end else begin
      $display("MAC unknown, flooding all ports");
      return -1;  // Flood
    end
  endfunction
endmodule

2. Cache Simulator

module cache_model;
  logic [31:0] cache [logic[31:0]];  // address → data
  int hits = 0;
  int misses = 0;
  
  task read(logic [31:0] addr, output logic [31:0] data);
    if (cache.exists(addr)) begin
      data = cache[addr];
      hits++;
      $display("Cache HIT:  addr=%h, data=%h", addr, data);
    end else begin
      data = read_from_memory(addr);  // Simulate memory read
      cache[addr] = data;  // Cache it
      misses++;
      $display("Cache MISS: addr=%h, data=%h", addr, data);
    end
  endtask
  
  function void print_stats();
    int total = hits + misses;
    real hit_rate = real'(hits) / real'(total) * 100.0;
    $display("Cache Statistics:");
    $display("  Hits: %0d", hits);
    $display("  Misses: %0d", misses);
    $display("  Hit Rate: %.2f%%", hit_rate);
  endfunction
endmodule

3. Scoreboard для верифікації

class scoreboard;
  typedef struct {
    logic [31:0] data;
    int timestamp;
    bit valid;
  } transaction_t;
  
  transaction_t expected [int];  // Transaction ID → expected data
  
  function void add_expected(int id, logic [31:0] data);
    expected[id] = '{data, $time, 1};
    $display("[%0t] Expected: ID=%0d, Data=%h", $time, id, data);
  endfunction
  
  task compare(int id, logic [31:0] actual);
    if (!expected.exists(id)) begin
      $error("Unexpected transaction: ID=%0d", id);
      return;
    end
    
    if (expected[id].data == actual) begin
      $display("[%0t] PASS: ID=%0d, Data=%h", $time, id, actual);
    end else begin
      $error("[%0t] FAIL: ID=%0d, Expected=%h, Actual=%h",
             $time, id, expected[id].data, actual);
    end
    
    expected.delete(id);  // Remove from scoreboard
  endtask
endclass

4. Sparse Memory Model

module sparse_memory #(
  parameter ADDR_WIDTH = 32,
  parameter DATA_WIDTH = 8
);
  logic [DATA_WIDTH-1:0] mem [logic[ADDR_WIDTH-1:0]];
  
  task write(logic [ADDR_WIDTH-1:0] addr, logic [DATA_WIDTH-1:0] data);
    mem[addr] = data;
    $display("Write: mem[%h] = %h", addr, data);
  endtask
  
  task read(logic [ADDR_WIDTH-1:0] addr, output logic [DATA_WIDTH-1:0] data);
    if (mem.exists(addr)) begin
      data = mem[addr];
    end else begin
      data = '0;  // Uninitialized memory returns 0
    end
    $display("Read:  mem[%h] = %h", addr, data);
  endtask
  
  function int get_used_size();
    return mem.num();  // Тільки реально використана пам'ять!
  endfunction
  
  // Приклад: 4GB address space, але займає пам'ять тільки для записаних адрес
  initial begin
    write(32'h0000_0000, 8'hAA);
    write(32'hFFFF_FFFF, 8'hBB);
    $display("Used only %0d bytes, not 4GB!", get_used_size());
  end
endmodule

Як запустити

Icarus Verilog (поточний симулятор)

iverilog -g2012 -o lab1d_unpacked_array lab1d_unpacked_array.sv
vvp lab1d_unpacked_array

Результат: Теоретичне пояснення (НЕ реальне виконання)

Questa/ModelSim

vlog -sv lab1d_unpacked_array.sv
vsim -c -do "run -all; quit" associative_array_demo

VCS

vcs -sverilog +v2k lab1d_unpacked_array.sv
./simv

Xcelium

xrun -sv lab1d_unpacked_array.sv

Ключові висновки

✅ Переваги Associative Array

  1. Швидкий пошук O(1) - hash table implementation
  2. Економія пам'яті - тільки використані ключі займають пам'ять
  3. Гнучкість ключів - будь-який тип: int, string, enum, struct
  4. Динамічний розмір - автоматично росте при додаванні
  5. Зручні методи - exists(), first(), next(), delete()

❌ Обмеження

  1. НЕ синтезується - тільки для тестбенчів!
  2. Потребує комерційний симулятор - Icarus Verilog не підтримує
  3. Непередбачуваний порядок - ітерація може відрізнятися між запусками
  4. Створення при зверненні - доступ до неіснуючого ключа створює запис

🎯 Використання

ДОБРЕ для:

  • Lookup tables (MAC tables, routing tables)
  • Sparse memory models
  • Scoreboards та checkers
  • Cache simulators
  • Test data structures

ПОГАНО для:

  • RTL дизайн (не синтезується!)
  • Коли потрібен гарантований порядок
  • Коли використовуєте Icarus Verilog

Порівняння з іншими мовами

Python Dictionary

mac_table = {}
mac_table["AA:BB:CC:DD:EE:01"] = 1
if "AA:BB:CC:DD:EE:02" in mac_table:
    port = mac_table["AA:BB:CC:DD:EE:02"]

C++ std::map

std::map<std::string, int> mac_table;
mac_table["AA:BB:CC:DD:EE:01"] = 1;
if (mac_table.find("AA:BB:CC:DD:EE:02") != mac_table.end()) {
    int port = mac_table["AA:BB:CC:DD:EE:02"];
}

SystemVerilog

int mac_table [string];
mac_table["AA:BB:CC:DD:EE:01"] = 1;
if (mac_table.exists("AA:BB:CC:DD:EE:02")) begin
  int port = mac_table["AA:BB:CC:DD:EE:02"];
end

Схожість: Всі використовують hash table для швидкого пошуку O(1).

Підсумок

Associative array - це потужний інструмент для верифікації SystemVerilog:

  • 🔑 Key-Value структура з динамічним розміром
  • ⚡ Швидкий пошук завдяки hash table
  • 💾 Економія пам'яті для sparse data
  • 🔧 Гнучкість у виборі типу ключа
  • ✅ Ідеально для тестбенчів і scoreboards

Але пам'ятайте:

⚠️ Тільки для верифікації, НЕ для синтезу!
⚠️ Потребує комерційний симулятор!

Версія: 1.0
Дата: 19 жовтня 2025 р.
Симулятор: Icarus Verilog 12.0 (теоретичне виконання)
Рекомендовано: Questa/VCS/Xcelium (реальне виконання)
Стандарт: SystemVerilog IEEE 1800-2012