1 {-# LANGUAGE TypeOperators, TemplateHaskell #-}
5 import System.IO.Unsafe (unsafePerformIO,unsafeInterleaveIO)
7 import qualified Prelude as P
8 import CLasH.HardwareTypes
9 import CLasH.Translator.Annotations
17 type DataInt = SizedWord DataSize
18 type ArrayIndex = SizedWord IndexSize
19 type Discr = RangedWord DiscrRange
21 type RAM a = Vector (DiscrRange :+: D1) a
23 type ReducerState = State ( DiscrState
28 type ReducerSignal = ( ( DataInt
34 type MemState a = State (RAM a)
36 type OutputSignal = ( (DataInt
42 type DiscrState = State ( ArrayIndex
46 type InputState = State ( Vector (AdderDepth :+: D1) ReducerSignal
47 , RangedWord AdderDepth
50 type FpAdderState = State (Vector AdderDepth ReducerSignal)
52 type OutputState = State ( MemState DataInt
58 Discriminator adds a discriminator to each input value
61 prev_index: previous index
62 cur_discr: current discriminator
70 discr: discriminator belonging to output value
71 new_discr: value of new discriminator, is -1 if cur_discr hasn't changed
72 index: Index belonging to the new discriminator
74 discriminator :: DiscrState -> (DataInt, ArrayIndex) ->
76 , ((DataInt, Discr), (Bit, ArrayIndex))
78 discriminator (State (prev_index,cur_discr)) (data_in, index) =
79 (State (prev_index', cur_discr'), ((data_in, discr),(new_discr, index)))
81 -- Update discriminator if index changes
82 cur_discr' | prev_index == index = cur_discr
83 | otherwise = cur_discr + 1
84 -- Notify OutputBuffer if a new discriminator becomes in use
85 new_discr | prev_index == index = Low
88 discr = fromSizedWord cur_discr'
91 Second attempt at Fifo
92 Uses "write pointer"... ugly...
93 Can potentially be mapped to hardware
96 mem: content of the FIFO
97 wrptr: points to first free spot in the FIFO
100 inp: (value,discriminator) pair
101 enable: Flushes 2 values from FIFO if 2, 1 value from FIFO if 1, no values
105 out1: ((value, discriminator),valid) pair of head FIFO
106 out2: ((value, discriminator),valid) pair of second register FIFO
108 valid indicates if the output contains a valid discriminator
110 inputBuffer :: InputState ->
111 ((DataInt, Discr), RangedWord D2) ->
112 (InputState, (ReducerSignal, ReducerSignal))
113 inputBuffer (State (mem,wrptr)) (inp,enable) = (State (mem',wrptr'),(out1, out2))
115 out1 = last mem -- output head of FIFO
116 out2 = last (init mem) -- output 2nd element
117 -- Update free spot pointer according to value of 'enable'
118 wrptr' | enable == 0 = wrptr - 1
119 | enable == 1 = wrptr
120 | otherwise = wrptr + 1
121 -- Write value to free spot
122 mem'' = replace mem wrptr (inp,High)
123 -- Flush values at head of fifo according to value of 'enable'
124 mem' | enable == 0 = mem''
125 | enable == 1 = zero +> (init mem'')
126 | otherwise = zero +> (zero +> (init(init mem'')))
127 zero = (((0::DataInt),(0::Discr)),(Low::Bit))
133 output discriminator becomes discriminator of the first operant
136 state: "pipeline" of the fp Adder
139 input1: out1 of the FIFO
140 input2: out2 of the FIFO
141 grant: grant signal comming from the controller, determines which value enters
143 mem_out: Value of the output buffer for the read address
144 Read address for the output buffer is the discriminator at the top of
148 output: ((Value, discriminator),valid) pair at the top of the adder pipeline
150 valid indicates if the output contains a valid discriminator
152 fpAdder :: FpAdderState ->
155 , (RangedWord D2, RangedWord D2)
158 (FpAdderState, ReducerSignal)
159 fpAdder (State state) (input1, input2, grant, mem_out) = (State state', output)
161 -- output is head of the pipeline
163 -- First value of 'grant' determines operant 1
164 operant1 | (fst grant) == 0 = fst (fst (last state))
165 | (fst grant) == 1 = fst (fst input2)
167 -- Second value of 'grant' determine operant 2
168 operant2 | (snd grant) == 0 = fst (fst input1)
169 | (snd grant) == 1 = fst (fst mem_out)
171 -- Determine discriminator for new value
172 discr | (snd grant) == 0 = snd (fst input1)
173 | (snd grant) == 1 = snd (fst (last state))
175 -- Determine if discriminator should be marked as valid
176 valid | grant == (2,2) = Low
178 -- Shift addition of the two operants into the pipeline
179 state' = (((operant1 + operant2),discr),valid) +> (init state)
183 first attempt at BlockRAM
186 mem: content of the RAM
189 data_in: input value to be written to 'mem' at location 'wraddr'
191 wraddr: write address
192 wrenable: write enable flag
195 data_out: value of 'mem' at location 'rdaddr'
197 {-# NOINLINE blockRAM #-}
198 blockRAM :: (MemState a) ->
205 blockRAM (State mem) (data_in, rdaddr, wraddr, wrenable) =
206 ((State mem'), data_out)
208 data_out = mem!rdaddr
209 -- Only write data_in to memory if write is enabled
210 mem' = case wrenable of
212 High -> replace mem wraddr data_in
215 Output logic - Determines when values are released from blockram to the output
218 mem: memory belonging to the blockRAM
219 lut: Lookup table that maps discriminators to Index'
220 valid: Lookup table for 'validity' of the content of the blockRAM
223 discr: Value of the newest discriminator when it first enters the system.
225 index: Index belonging to the newest discriminator
226 data_in: value to be written to RAM
228 wraddr: write address
229 wrenable: write enabled flag
232 data_out: value of RAM at location 'rdaddr'
233 output: Reduced row when ready, (-1) otherwise
235 outputter :: OutputState ->
244 (OutputState, (ReducerSignal, OutputSignal))
245 outputter (State (mem1, mem2, lut, valid))
246 (discr, index, new_discr, data_in, rdaddr, wraddr, wrenable) =
247 ((State (mem1', mem2', lut', valid')), (data_out, output))
249 -- Lut is updated when new discriminator/index combination enters system
250 lut' | new_discr /= Low = replace lut discr index
252 -- Location becomes invalid when Reduced row leaves system
253 valid'' | (new_discr /= Low) && ((valid!discr) /= Low) =
254 replace valid discr Low
256 -- Location becomes invalid when it is fed back into the pipeline
257 valid' | wrenable == Low = replace valid'' rdaddr Low
258 | otherwise = replace valid'' wraddr High
259 (mem1', mem_out1) = blockRAM mem1 ( data_in
264 (mem2', mem_out2) = blockRAM mem2 ( data_in
269 data_out = ( ( (mem_out1)
274 -- Reduced row is released when new discriminator enters system
275 -- And the position at the discriminator holds a valid value
276 output = ( ( (mem_out2)
279 , (new_discr `hwand` (valid!discr))
283 Arbiter determines which rules are valid
286 fp_out: output of the adder pipeline
287 mem_out: data_out of the output logic
288 inp1: Head of the input FIFO
289 inp2: Second element of input FIFO
292 r4 - r0: vector of rules, rule is invalid if it's 0, valid otherwise
294 arbiter :: (ReducerSignal, ReducerSignal, ReducerSignal, ReducerSignal) ->
296 arbiter (fp_out, mem_out, inp1, inp2) = (r4 +> (r3 +> (r2 +> (r1 +> (singleton r0)))))
297 where -- unpack parameters
298 fp_valid = snd fp_out
299 next_valid = snd mem_out
300 inp1_valid = snd inp1
301 inp2_valid = snd inp2
302 fp_discr = snd (fst fp_out)
303 next_discr = snd (fst mem_out)
304 inp1_discr = snd (fst inp1)
305 inp2_discr = snd (fst inp2)
307 r0 | (fp_valid /= Low) && (next_valid /= Low) && (fp_discr == next_discr)
310 r1 | (fp_valid /= Low) && (inp1_valid /= Low) && (fp_discr == inp1_discr)
313 r2 | (inp1_valid /= Low) && (inp2_valid /= Low) &&
314 (inp1_discr == inp2_discr) = High
316 r3 | inp1_valid /= Low = High
321 Controller determines which values are fed into the pipeline
322 and if the write enable flag for the Output RAM should be set
323 to true. Also determines how many values should be flushed from
327 fp_out: output of the adder pipeline
328 mem_out: data_out of the output logic
329 inp1: Head of input FIFO
330 inp2: Second element of input FIFO
333 grant: Signal that determines operants for the adder
334 enable: Number of values to be flushed from input buffer
335 wr_enable: Determine if value of the adder should be written to RAM
337 controller :: (ReducerSignal, ReducerSignal, ReducerSignal, ReducerSignal) ->
338 ((RangedWord D2, RangedWord D2), RangedWord D2, Bit)
339 controller (fp_out,mem_out,inp1,inp2) = (grant,enable,wr_enable)
341 -- Arbiter determines which rules are valid
342 valid = arbiter (fp_out,mem_out,inp1,inp2)
343 -- Determine which values should be fed to the adder
344 grant = if (valid!(4 :: RangedWord D4) == High)
346 else if ((drop d3 valid) == $(vectorTH [High,Low]))
348 else if ((drop d2 valid) == $(vectorTH [High,Low,Low]))
350 else if ((drop d1 valid) == $(vectorTH [High,Low,Low,Low]))
353 -- Determine if some values should be flushed from input FIFO
354 enable = if (grant == (1,0))
356 else if ((grant == (0,0)) || (grant == (2,0)))
359 -- Determine if the output value of the adder should be written to RAM
360 wr_enable' = if (valid!(4 :: RangedWord D4) == High)
362 else if ((drop d3 valid) == $(vectorTH [High,Low]))
364 else if ((drop d2 valid) == $(vectorTH [High,Low,Low]))
366 else if ((drop d1 valid) == $(vectorTH [High,Low,Low,Low]))
369 wr_enable = if ((snd fp_out) /= Low) then wr_enable' else Low
374 Combines all the earlier defined functions. Uses the second implementation
378 'n': specifies the max discriminator value.
380 State: all the states of the used functions
382 Input: (value,index) combination
386 {-# ANN reducer TopEntity #-}
387 reducer :: ReducerState ->
388 (DataInt, ArrayIndex) ->
389 (ReducerState, OutputSignal)
390 reducer (State (discrstate,inputstate,fpadderstate,outputstate)) input =
391 (State (discrstate',inputstate',fpadderstate',outputstate'),output)
393 (discrstate', discr_out) = discriminator discrstate input
394 (inputstate',(fifo_out1, fifo_out2)) = inputBuffer inputstate (
395 (fst discr_out), enable)
396 (fpadderstate', fp_out) = fpAdder fpadderstate (fifo_out1,
397 fifo_out2, grant, mem_out)
398 discr = snd (fst discr_out)
399 new_discr = fst (snd discr_out)
400 index = snd (snd discr_out)
401 rdaddr = snd (fst fp_out)
403 data_in = fst (fst fp_out)
404 (outputstate', (mem_out, output)) = outputter outputstate (discr,
405 index, new_discr, data_in, rdaddr,
407 (grant,enable,wr_enable) = controller (fp_out, mem_out,
408 fifo_out1, fifo_out2)
411 -- -------------------------------------------------------
413 -- -------------------------------------------------------
415 -- "Default" Run function
416 run func state [] = []
417 run func state (i:input) = o:out
419 (state', o) = func state i
420 out = run func state' input
422 -- -- "Special" Run function, also outputs new state
423 -- run' func state [] = ([],[])
424 -- run' func state (i:input) = ((o:out), (state':ss))
426 -- (state',o) = func state i
427 -- (out,ss) = run' func state' input
430 runReducer = ( reduceroutput
437 output = run reducer istate input
438 reduceroutput = P.map fst (filter (\x -> (snd x) /= Low) output)
439 validoutput = [P.foldl (+) 0
440 (P.map (\z -> toInteger (fst z))
441 (filter (\x -> (snd x) == i) input)) | i <- [0..10]]
442 equal = [validoutput!!i == toInteger (fst (reduceroutput!!i)) |
445 -- -- Generate infinite list of numbers between 1 and 'x'
446 -- randX :: Integer -> [Integer]
447 -- randX x = randomRs (1,x) (unsafePerformIO newStdGen)
449 -- -- Generate random lists of indexes
450 -- randindex 15 i = randindex 1 i
451 -- randindex m i = (P.take n (repeat i)) P.++ (randindex (m+1) (i+1))
453 -- [n] = P.take 1 rnd
454 -- rnd = randomRs (1,m) (unsafePerformIO newStdGen)
456 -- -- Combine indexes and values to generate random input for the reducer
457 -- randominput n x = P.zip data_in index_in
459 -- data_in = P.map (fromInteger :: Integer -> DataInt) (P.take n (randX x))
460 -- index_in = P.map (fromInteger :: Integer -> ArrayIndex)
461 -- (P.take n (randindex 7 0))
464 -- putStrLn (show runReducer)
466 -- simulate f input s = do
468 -- putStr $ show input
469 -- putStr "\nInitial State: "
472 -- foldl1 (>>) (map (printOutput) output)
474 -- output = run f input s
476 initstate :: ReducerState
478 ( State ( (255 :: ArrayIndex)
479 , (7 :: SizedWord DiscrSize)
481 , State ( copy ((0::DataInt,0::Discr),Low)
482 , (2 :: RangedWord AdderDepth)
484 , State (copy ((0::DataInt,0::Discr),Low))
485 , State ( State (copy (0::DataInt))
486 , State (copy (0::DataInt))
487 , (copy (0::ArrayIndex))
492 siminput :: [(DataInt, ArrayIndex)]
493 siminput = [(13,0),(7,0),(14,0),(14,0),(12,0),(10,0),(19,1),(20,1),(13,1)
494 ,(5,1),(9,1),(16,1),(15,1),(10,2),(13,2),(3,2),(9,2),(19,2),(5,3)
495 ,(5,3),(10,3),(17,3),(14,3),(5,3),(15,3),(11,3),(5,3),(1,3),(8,4)
496 ,(20,4),(8,4),(1,4),(11,4),(10,4),(13,5),(18,5),(5,5),(6,5),(6,5)
497 ,(4,6),(4,6),(11,6),(11,6),(11,6),(1,6),(11,6),(3,6),(12,6),(12,6)
498 ,(2,6),(14,6),(11,7),(13,7),(17,7),(9,7),(19,8),(4,9),(18,10)
499 ,(6,10),(18,11),(1,12),(3,12),(14,12),(18,12),(14,12),(6,13)
500 ,(9,13),(11,14),(4,14),(1,14),(14,14),(14,14),(6,14),(11,15)
501 ,(13,15),(7,15),(2,16),(16,16),(17,16),(5,16),(20,16),(17,16)
502 ,(14,16),(18,17),(13,17),(1,17),(19,18),(1,18),(20,18),(4,18)
503 ,(5,19),(4,19),(6,19),(19,19),(4,19),(3,19),(7,19),(13,19),(19,19)