Your task is to predict the maximum performance that you can achieve if you implement the following pseudocode in hardware with a single-port memory array in Question a and with a dual-port memory array in Question b.
for i := 0 to 254
{
if A[i] > A[i+1] then
{
tmp := A[i+1];
A[i+1] := A[i];
A[i] := tmp;
}
}
Question a: If you use a single-port memory array, what is the minimum number of clock cycles that your circuit will need to perform the above loop?
Question b: If you use a dual-port memory with one read port and one read/write port, what is the minimum number of clock cycles that your circuit will need to perform the above loop?
for i := 0 to 254
{
if A[i] > A[i+1] then
{
tmp := A[i+1];
A[i+1] := A[i];
A[i] := tmp;
}
}
Question a: If you use a single-port memory array, what is the minimum number of clock cycles that your circuit will need to perform the above loop?
Question b: If you use a dual-port memory with one read port and one read/write port, what is the minimum number of clock cycles that your circuit will need to perform the above loop?
For single port memories, we can access - read - one address on each clock cycle. For the start of the loop, we will spend two cycles to read a[0] & a[1]. The minimal number of clock cycles will happen if the memory is already sorted. For the next access, we just need to access a[2], a[1] is already available. So totally 255 clock cycles will be needed.
ReplyDeleteFor dual port, for the first step in the loop, both a[0] & a[1] can be accessed in one cycle. We don't have any space to hold more than two pieces of data - so it will be one read per cycle, and a total of 254 clock cycles will be needed