From 0452c2e3ecd32ee6d9c7dada179c86f02a0585be Mon Sep 17 00:00:00 2001 From: whitequark Date: Mon, 23 Sep 2019 10:57:30 +0000 Subject: [PATCH] lib.fifo: round up AsyncFIFO{,Buffered} depth to lowest valid value. Unless exact_depth=True is specified. The logic introduced in this commit is idempotent: that is, if one uses the depth of one AsyncFIFOBuffered in the constructor of another AsyncFIFOBuffered, they will end up with the same depth. More naive logic would result in an unbounded, quadratic growth with each such step. Fixes #219. --- nmigen/lib/fifo.py | 38 +++++++++++++++++++++++--------- nmigen/test/test_lib_fifo.py | 42 +++++++++++++++++++++++++++++++++++- 2 files changed, 69 insertions(+), 11 deletions(-) diff --git a/nmigen/lib/fifo.py b/nmigen/lib/fifo.py index 9be6003..f157d65 100644 --- a/nmigen/lib/fifo.py +++ b/nmigen/lib/fifo.py @@ -61,6 +61,9 @@ class FIFOInterface: r_attributes="") def __init__(self, width, depth, *, fwft): + if depth <= 0: + raise ValueError("FIFO depth must be positive, not {}".format(depth)) + self.width = width self.depth = depth self.fwft = fwft @@ -258,7 +261,7 @@ class SyncFIFOBuffered(Elaboratable, FIFOInterface): This queue's interface is identical to :class:`SyncFIFO` configured as ``fwft=True``, but it does not use asynchronous memory reads, which are incompatible with FPGA block RAMs. - In exchange, the latency betw_enen an entry being written to an empty queue and that entry + In exchange, the latency between an entry being written to an empty queue and that entry becoming available on the output is increased by one cycle compared to :class:`SyncFIFO`. """.strip(), parameters=""" @@ -312,6 +315,9 @@ class AsyncFIFO(Elaboratable, FIFOInterface): Read and write interfaces are accessed from different clock domains, which can be set when constructing the FIFO. + + :class:`AsyncFIFO` only supports power of 2 depths. Unless ``exact_depth`` is specified, + the ``depth`` parameter is rounded up to the next power of 2. """.strip(), parameters=""" r_domain : str @@ -327,16 +333,18 @@ class AsyncFIFO(Elaboratable, FIFOInterface): r_attributes="", w_attributes="") - def __init__(self, width, depth, *, r_domain="read", w_domain="write"): - super().__init__(width, depth, fwft=True) + def __init__(self, width, depth, *, r_domain="read", w_domain="write", exact_depth=False): + try: + depth_bits = log2_int(depth, need_pow2=exact_depth) + except ValueError as e: + raise ValueError("AsyncFIFO only supports depths that are powers of 2; requested " + "exact depth {} is not" + .format(depth)) from None + super().__init__(width, 1 << depth_bits, fwft=True) self._r_domain = r_domain self._w_domain = w_domain - - try: - self._ctr_bits = log2_int(depth, need_pow2=True) + 1 - except ValueError as e: - raise ValueError("AsyncFIFO only supports power-of-2 depths") from e + self._ctr_bits = depth_bits + 1 def elaborate(self, platform): # The design of this queue is the "style #2" from Clifford E. Cummings' paper "Simulation @@ -419,6 +427,10 @@ class AsyncFIFOBuffered(Elaboratable, FIFOInterface): Read and write interfaces are accessed from different clock domains, which can be set when constructing the FIFO. + :class:`AsyncFIFOBuffered` only supports power of 2 plus one depths. Unless ``exact_depth`` + is specified, the ``depth`` parameter is rounded up to the next power of 2 plus one. + (The output buffer acts as an additional queue element.) + This queue's interface is identical to :class:`AsyncFIFO`, but it has an additional register on the output, improving timing in case of block RAM that has large clock-to-output delay. @@ -439,8 +451,14 @@ class AsyncFIFOBuffered(Elaboratable, FIFOInterface): r_attributes="", w_attributes="") - def __init__(self, width, depth, *, r_domain="read", w_domain="write"): - super().__init__(width, depth, fwft=True) + def __init__(self, width, depth, *, r_domain="read", w_domain="write", exact_depth=False): + try: + depth_bits = log2_int(max(0, depth - 1), need_pow2=exact_depth) + except ValueError as e: + raise ValueError("AsyncFIFOBuffered only supports depths that are one higher " + "than powers of 2; requested exact depth {} is not" + .format(depth)) from None + super().__init__(width, (1 << depth_bits) + 1, fwft=True) self._r_domain = r_domain self._w_domain = w_domain diff --git a/nmigen/test/test_lib_fifo.py b/nmigen/test/test_lib_fifo.py index 93ad95b..527a152 100644 --- a/nmigen/test/test_lib_fifo.py +++ b/nmigen/test/test_lib_fifo.py @@ -5,6 +5,46 @@ from ..back.pysim import * from ..lib.fifo import * +class FIFOTestCase(FHDLTestCase): + def test_depth_wrong(self): + with self.assertRaises(ValueError, + msg="FIFO depth must be positive, not -1"): + FIFOInterface(width=8, depth=-1, fwft=True) + with self.assertRaises(ValueError, + msg="FIFO depth must be positive, not 0"): + FIFOInterface(width=8, depth=0, fwft=True) + + def test_async_depth(self): + self.assertEqual(AsyncFIFO(width=8, depth=1 ).depth, 1) + self.assertEqual(AsyncFIFO(width=8, depth=2 ).depth, 2) + self.assertEqual(AsyncFIFO(width=8, depth=3 ).depth, 4) + self.assertEqual(AsyncFIFO(width=8, depth=4 ).depth, 4) + self.assertEqual(AsyncFIFO(width=8, depth=15).depth, 16) + self.assertEqual(AsyncFIFO(width=8, depth=16).depth, 16) + self.assertEqual(AsyncFIFO(width=8, depth=17).depth, 32) + + def test_async_depth_wrong(self): + with self.assertRaises(ValueError, + msg="AsyncFIFO only supports depths that are powers of 2; " + "requested exact depth 15 is not"): + AsyncFIFO(width=8, depth=15, exact_depth=True) + + def test_async_buffered_depth(self): + self.assertEqual(AsyncFIFOBuffered(width=8, depth=1 ).depth, 2) + self.assertEqual(AsyncFIFOBuffered(width=8, depth=2 ).depth, 2) + self.assertEqual(AsyncFIFOBuffered(width=8, depth=3 ).depth, 3) + self.assertEqual(AsyncFIFOBuffered(width=8, depth=4 ).depth, 5) + self.assertEqual(AsyncFIFOBuffered(width=8, depth=15).depth, 17) + self.assertEqual(AsyncFIFOBuffered(width=8, depth=16).depth, 17) + self.assertEqual(AsyncFIFOBuffered(width=8, depth=17).depth, 17) + self.assertEqual(AsyncFIFOBuffered(width=8, depth=18).depth, 33) + + def test_async_buffered_depth_wrong(self): + with self.assertRaises(ValueError, + msg="AsyncFIFOBuffered only supports depths that are one higher than powers of 2; " + "requested exact depth 16 is not"): + AsyncFIFOBuffered(width=8, depth=16, exact_depth=True) + class FIFOModel(Elaboratable, FIFOInterface): """ Non-synthesizable first-in first-out queue, implemented naively as a chain of registers. @@ -211,4 +251,4 @@ class FIFOFormalCase(FHDLTestCase): self.check_async_fifo(AsyncFIFO(width=8, depth=4)) def test_async_buffered(self): - self.check_async_fifo(AsyncFIFOBuffered(width=8, depth=3)) + self.check_async_fifo(AsyncFIFOBuffered(width=8, depth=4)) -- 2.30.2