Memory Dependency Handling

[Sibylau]

Memory dependencies are common in various applications. One example I encountered is:

import heterocl as hcl
import numpy as np

N_HASH_FUNC = 5
HASH_RANGE = 10
PACKET_SIZE = 10

def func_wrapper(dtype):
    hcl.init(dtype)
    
    a=hcl.placeholder((N_HASH_FUNC,), dtype=dtype, name="a")
    b=hcl.placeholder((N_HASH_FUNC,), dtype=dtype, name="b")
    key=hcl.placeholder((PACKET_SIZE,), dtype=dtype, name="key")

    def hash_index(a, b, key):
        sketch = hcl.compute((N_HASH_FUNC, HASH_RANGE), lambda x,y: 0, name="sketch")
        with hcl.for_(0, PACKET_SIZE) as p:
            key_local = hcl.compute((1,), lambda x: key[p], name = "key_local")
            index = hcl.compute(a.shape, lambda x: (a[x]*key_local[0] + b[x])%HASH_RANGE, name="index")
            with hcl.for_(0, N_HASH_FUNC) as i:
                sketch[i][index[i]] += 1
    
    s = hcl.create_schedule([a, b, key], hash_index)
    target = hcl.Platform.asic_hls
    target.config(compile="catapultc", mode="sw_sim")
    s.to([a, b], target.xcel, mode=hcl.IO.DMA)
    s.to(key, target.xcel, mode=hcl.IO.Stream)
    f = hcl.build(s, target, name='countmin')

    np_a = np.random.randint(10, size=(N_HASH_FUNC,))
    np_b = np.random.randint(10, size=(N_HASH_FUNC,))
    np_key = np.random.randint(10, size=(PACKET_SIZE,))
    args = (np_a, np_b, np_key)
    f.inspect(args)

if __name__ == "__main__":
    func_wrapper(hcl.Int(32))

The key issue here is when writing sketch[i][index[i]] += 1, the generated HLS code has similar syntax in the loop, which introduces memory dependency and leads to poor performance. In this case, it is a real memory dependency since the access of the sketch array depends on the value in index , and continuous iterations can update the value in the same memory address.

There are several problems if we are handling such memory dependencies in the framework: 1. Identify variables that introduce memory dependency One solution is to let users specify which arrays are susceptible to data dependencies. Another way is to detect memory dependencies automatically in the HeteroCL framework, which seems not quite straightforward to me.

2. Handle false memory dependency Typically in HLS tools, there are pragmas and tcl commands that rule out false memory dependencies from our concerns, and we can add such pragmas or tcl commands in the codegen framework.

3. Handle real memory dependency One technique to solve RAW memory dependency in a pipeline is inserting data forwarding logic. Is it possible to enable hazard handling automatically (and if so, at which IR level)? Or throw out a critical warning for users to think about writing relevant logic in HeteroCL code?