SystemVerilog Dynamic Arrays and Queues
In this post, we talk about the different types of dynamic arrays we can use in SystemVerilog, including normal dynamic arrays and their associated methods, queues and their associated methods and finally associative arrays.
As we talked about in a previous post, we can declare either static or dynamic arrays in SystemVerilog.
When we declare a static array, a fixed amount of memory is allocated to the array at compile time. We have discussed SystemVerilog static arrays in depth in a previous blog post.
In contrast, we can allocate extra memory or resize a dynamic array while a simulation is running. As a result of this, we can only use dynamic arrays in our testbench code and not in synthesizable code.
In the rest of this post we talk about the way we can use dynamic arrays in our SystemVerilog code.
There are actually three different types of dynamic array which we can use in SystemVerilog – dynamic arrays, queues and associative arrays.
We use each of these three types of array to perform a slightly different task in our testbench. We discuss all three of these arrays in more detail int he rest of this post
SystemVerilog Dynamic Arrays
SystemVerilog dynamic arrays are a special class of array which can be resized whilst a simulation is running.
This differentiates them from static arrays which are allocated memory during compile time and have a fixed sized for the duration of a simulation.
This is useful as we may have instances where we don’t know exactly how many elements our array will require when we compile our code.
The code snippet below shows how we declare a dynamic array in SystemVerilog.
// General syntax to declare a dynamic array <type> <size> <variable_name> [];
When we create a dynamic array, we must always declare it as an unpacked type array.
As dynamic arrays are initially empty, we have to use the new keyword to allocate memory to the array before we can use it. We also declare the number of elements in the array when we use the new keyword.
The code example below shows how we would declare a dynamic array and then allocate the memory for 4 elements.
// Declare a dynamic array logic [7:0] example []; // Allocate memory to the array example = new[4];
Dynamic Array Methods
Dynamic arrays are slightly more complex to work with than static arrays as we have to manage the size of the array in our code.
As a result of this, a number of methods are included in the SystemVerilog to help us manage dynamic arrays.
We have already seen one of the most important of these methods in the previous section – the new method.
In addition to this, we also commonly use the delete and size methods to manage our dynamic arrays.
Let’s take a closer a look at each of these methods in more detail.
The new Method
As we have previously seen, we use the new method to allocate memory to our dynamic array.
The code snippet below shows the general syntax we use to call the new method.
// General syntax for the new method <name> = new[ <size> ] ( <value> );
The <size> field in this construct is used to specify how many elements there will be in the array.
We use the <values> field to assign values to the array after it has allocated memory. We can exclude this field if we are creating an empty array.
For example, we would use the code shown below to allocate memory for 8 elements in a dynamic array.
// Declaration of the example array logic [7:0] example []; // Allocate memory for 8 elements example = new[8];
We can call the new method as many times as necessary in our code. Each time we call the new method, we effectively create a new array and allocate memory to it.
For example, we might need to replace our array of 8 elements with a new array which has 16 elements. In this case, we would simply call the new method a second time to resize our array.
The code snippet below shows how we would use the new method to do this.
// Declaration of the example array logic [7:0] example []; // Allocate memory for 8 elements example = new[8]; // Resize the array to 16 elements example = new[16];
When we use the new method in this way, any contents which were in the old array are deleted. This means that we create an entirely new, empty array when using this method.
However, we can also keep the existing contents of our array when we call the new method.
To do this, we need to pass the existing array to the new method using the <value> field we mentioned before. This will place the contents of the old array at the start of the resized array.
For example, suppose that we had created a dynamic array which consists of 8 elements and assigned some data to it.
If we now wanted to resize the array to 16 elements and keep the existing data, we could do this using the code shown below. This code can also be simulated on eda playground.
// Declaration of the example array logic [7:0] example []; // Allocate memory for 8 elements example = new[8]; // Resize the array to 16 elements example = new[16](example);
The delete Method
We use the delete method to remove the entire contents of a dynamic array.
When we call this method, it not only deletes the contents of the dynamic array but also deallocate the memory. In this sense, we can consider the delete method to be roughly equivalent to the free function in C.
The code snippet below shows the general syntax of the delete method.
// General syntax for the delete method <name>.delete();
In this construct, the <name> field is used to identify the dynamic array which we are calling the method on.
The SystemVerilog code below shows how we would use the delete method in practise. This code can also be simulated on eda playground.
// Declaration of the example array logic [7:0] example []; // Allocate memory for 8 elements example = new[8]; // Deallocate the array memory example.delete();
The size Method
We use the size method to determine how large our dynamic array is at any given time.
When we call this method it returns a value which is equal to the number of elements in an array.
As we can see from this, it performs a similar function to the $size macro which we mentioned in the post on static arrays.
The code snippet below shows the general syntax for this method.
// General syntax for the size method <name>.size();
In this construct, the <name> field is used to identify the dynamic array which we are calling the method on.
The SystemVerilog code below shows how we would use the size method in practise. This code can also be simulated on eda playground.
// Declaration of the example array logic [7:0] example []; // Allocate memory for 8 elements example = new[8]; // Use the size method to get the number of elements example.size();
SystemVerilog Queues
SystemVerilog queues are a type of array which are automatically resized when we add or remove elements to the array.
The code snippet below shows how we would declare a queue type in SystemVerilog.
// General syntax to declare a queue in SystemVerilog <type> <variable_name> [$:<max_length>];
In this construct, we use the $ symbol inside of square brackets to indicate that we are creating a queue type.
We use the optional <max_length> field to limit the amount of elements which a queue can have.
However, we often exclude the <max_length> field from our declaration. When we do this, our queue can contain an unlimited amount of elements.
Queues which have an unlimited amount of elements are known as unbounded arrays whilst queues which are declared using the <max_length> field are known as bounded arrays.
When we declare a queue we can initialize it using a comma separated list of values between a pair of curly braces. This is similar to the use of array literals which we discussed in the previous post.
The SystemVerilog code below shows how we declare both a bounded and an unbounded queue. We also initialize both of the example queues with 2 elements.
// Declaration and initialization of a bounded queue
int example_b [$:255] = { 0, 1 };
// Declaration and initialization of an unbounded queue
int example_ub [$] = { 2, 3 };Dynamic Arrays vs Queues
Dynamic arrays and queues actually perform very similar functions in SystemVerilog as they are both allocated memory at run time. As a result of this, we can resize both of these data structures whilst our code is running.
However, we use them for different purposes as they are optimized for slightly different operations.
We use queues when we are only interested in adding or removing elements at the beginning or end of the array.
The reason for this is that dynamic arrays are stored in contiguous memory addresses during simulation. As a result of this, when we resize a dynamic array it is often necessary for the entire array to be moved to a new location in memory.
In contrast, SystemVerilog queues are implemented in a similar way to linked lists in other programming languages.
This means that it is much quicker to add or remove elements to a queue as there is no need to move the existing elements in the array.
We typically use SystemVerilog queues to emulate either FIFO or LIFO type memories. We often see queues used in this way to move transactions between different blocks in a SystemVerilog based testbench.
However, when we want to access elements in the middle of the data structure then dynamic arrays are more efficient
The reason for this is that our simulator must start from either the beginning or end of the queue and loop through the memory until it reaches the required element. Again, this behavior is similar to linked lists in other programming languages.
In contrast, our simulator can directly access any element in dynamic array.
As we can see from this, it is clearly much quicker for our simulator to retrieve data from the middle of a dynamic array as less memory accesses are required.
Queue Methods
SystemVerilog queues are more complex that static arrays due to the fact that they require dynamic memory allocation.
As a result of this, we have a number of in built methods which can use to manipulate the contents of our queue.
This is in contrast to arrays where we can directly access individual elements to manipulate the contents of the array.
Let’s take a closer a look at the most important queue methods in SystemVerilog.
Push to Queue
When we want to add data to a SystemVerilog queue, we can use either the push_front or the push_back method.
The push_front method inserts the specified data onto the front of the queue whilst the push_back method inserts the data at the end fo the queue.
We can think of the front of the queue as being equivalent to the lowest indexed element of a normal array.
In contrast, when we talk about the back of a queue this is equivalent to the highest indexed element of a normal array type.
The picture below illustrates the concept of push_front and push_back queue methods.
The code snippet below shows the general syntax we use to call the push_front and push_back methods.
// General syntax for the push_front method <queue_name>.push_front( <value> ); // General syntax for the push_back method <queue_name>.push_back( <value> );
In this construct we use the <queue_name> field to identify the queue we are adding data to.
We then use the <value> field to specify the value of the data which we are adding to the queue. We can use either a hard coded value or a variable to add data to our queue.
The SystemVerilog code below shows how we use the push_front and push_back methods in practise. This code can also be simulated on eda playground.
// Create a queue with some initial values in it
int example_q [$] = { 1, 2 };
// Push a value into the front of the queue
example_q.push_front(0);
// Push a value into the back of the queue
// i will be equal to 3 after this operation
example_q.push_back(3);Pop From Queue
When we want to get some data from a SystemVerilog queue we use either the pop_front or pop_back methods.
The pop_front method retrieves data from the front of the queue whilst the pop_back method retrieves the data at the end fo the queue.
As with push_front method, the front of the queue is equivalent to the lowest indexed element of a normal array.
In constrast, the back of a queue is equivalent to the highest indexed element of a normal array type.
When we call either of these methods, the required element is removed from the queue and the value of this element is returned by the function.
The picture below illustrates the concept of pop_front and pop_back queue methods.
The code snippet below shows the general syntax we use to call the pop_front and pop_back methods.
// General syntax for the pop_front method <queue_name>.pop_front(); // General syntax for the pop_back method <queue_name>.push_back();
In this construct we use the <queue_name> field to identify the queue we are retrieving data from.
The SystemVerilog code below shows how we use the pop_front and pop_back methods in practise. We can also simulate this code on eda playground.
// Create a queue with some initial values in it
int example_q [$] = { 0, 1, 2, 3 };
int i;
// Pop a value from the front of the queue
// i will be equal to 0 after this operation
i = example_q.pop_front;
// Pop a value from the front of the queue
// i will be equal to 3 after this operation
i = example_q.pop_back;Insert and Delete Methods
We can also use the insert and delete methods to add or remove an element in a SystemVerilog queue.
In contrast to the push and pop methods, we use these two methods to add or remove elements at a specific location in the queue.
As a result, we can use these methods to modify elements in the middle of our array.
However, we should be aware that these methods are less efficient than the push and pop methods. In addition, they can also be inefficient in comparison to the equivalent methods in dynamic arrays.
In fact, when we make extensive use of the insert or delete methods this may be a good indication that we should be using a dynamic array instead.
The code snippet below shows the general syntax we use to call the insert and delete methods.
// General syntax for the pop_front method <queue_name>.pop_front(); // General syntax for the pop_back method <queue_name>.push_back();
In this construct we use the <queue_name> field to identify the queue which we are modifying.
We use the <value> field to specify the value of the data which we are adding to the queue. We can use either a hard coded value or a variable to add data to our queue.
In the case of the insert method, we use the <index> field to specify where the new element will be inserted in our queue.
In the case of the delete method, we use the <index> field to specify which element of the queue will be removed.
However, we can omit the <index> field when we use the delete method. When we do this, the entire content of our queue will be deleted.
The SystemVerilog code below shows how we use the insert and delete methods in practise. This code can also be simulated on eda playground.
// Create a queue with some initial values in it
int example_q [$] = { 1, 2 };
// Insert a value into the SystemVerilog Associative Arrays
The final type of array which we can use in SystemVerilog is the associative array.
When we declare an associative array, memory for the array is not allocated at compile time and we can resize the array during simulation.
Therefore, associative arrays are very similar to the dynamic arrays which we discussed previously in this post.
However, the way that we index associative arrays is different from the way that we index dynamic arrays.
As we previously saw, we use sequential integers to index different elements of a dynamic array.
In contrast, we can use any value that we want to index the different elements of an associative array in SystemVerilog.
For example, we could use non sequential integers if we wanted to model the contents of a sparsely populated memory.
However, we could also use a string to give a physical name to the indexes in an associative array.
As we can see from this, we can think of associative arrays as being roughly equivalent to key-value pairs in other programming languages.
The SystemVerilog below shows the general syntax we use to declare an associative array.
// General syntax to declare an associative array <data_type> <array_name> [<key_type>];
When we use associative arrays, we must use the same data type for all of the indexes. This means that we can’t mix int types and strings, for example.
We use the <key_type> field to declare what data type we will use for the index.
When we use associative arrays in our SystemVerilog code, the simulator has to search for the memory location of each element in the array when we either read or write to it.
As a result of this, associative arrays are less efficient than both static and dynamic arrays. This normally results in slowly execution times for our test benches.
Therefore, we generally prefer to use either a static or dynamic array instead of associative arrays whenever it is possible.
Assigning Data to an Associative Array
We can assign values to an associative array using the same techniques which we discussed in the previous post.
However, when we use array literals to we have to specify not only the data which we are assigning but also the value of the index we want associated with that data.
The SystemVerilog code below shows the general syntax we use to assign data to an associative array using array literals.
// General syntax for array literals
<array_name> = '{ <key> : <data>, <key> : <data> };In this construct, we use the <key> field to set the value of the index in the array. The <data> field is then used to set the value of the data which is written to the array.
We can also use square brackets to access elements in an associative array. The syntax for this is exactly the same as we use for both static and dynamic arrays.
The SystemVerilog code below shows how we use associative arrays in practise. This code can also be simulated on eda playground.
// Create an associative array and initialize it
int example [string] = '{ "age" : 30, "height" : 190 };
// Add another element to the array
example["weight"] = 100;
// Read a value from the array
example["age"];