X-Git-Url: https://git.stderr.nl/gitweb?p=matthijs%2Fmaster-project%2Fc%CE%BBash.git;a=blobdiff_plain;f=reducer.hs;h=dfbc8424474fd2db2148c138abad5b999eae0d53;hp=ecc0051c3a896dfb9407a3a0346ff4d720e71d81;hb=3f39038911a675d91b5147761e16296d3ab25743;hpb=a533335368e252544db4f68ee03e0e7b7255eae5 diff --git a/reducer.hs b/reducer.hs index ecc0051..dfbc842 100644 --- a/reducer.hs +++ b/reducer.hs @@ -1,460 +1,368 @@ -{-# LANGUAGE TypeOperators, TemplateHaskell, FlexibleContexts, TypeFamilies #-} +{-# LANGUAGE TypeOperators, TemplateHaskell, FlexibleContexts, TypeFamilies, + ScopedTypeVariables, RecordWildCards #-} module Reducer where -import System.Random -import System.IO.Unsafe (unsafePerformIO,unsafeInterleaveIO) - import qualified Prelude as P import CLasH.HardwareTypes import CLasH.Translator.Annotations -type DataSize = D8 -type IndexSize = D8 -type DiscrSize = D3 -type DiscrRange = D7 -type AdderDepth = D2 - -type DataInt = SizedWord DataSize -type ArrayIndex = SizedWord IndexSize -type Discr = RangedWord DiscrRange - -type ReducerState = State ( DiscrState - , InputState - , FpAdderState - , OutputState - ) -type ReducerSignal = ( ( DataInt - , Discr - ) - , Bit - ) - -type OutputSignal = ( (DataInt - , ArrayIndex - ) - , Bit - ) - -type DiscrState = State ( ArrayIndex - , SizedWord DiscrSize - ) - -type InputState = State ( Vector (AdderDepth :+: D1) ReducerSignal - , RangedWord AdderDepth - ) - -type FpAdderState = State (Vector AdderDepth ReducerSignal) - -type OutputState = State ( MemState DiscrRange DataInt - , MemState DiscrRange DataInt - , MemState DiscrRange ArrayIndex - , RAM DiscrRange Bit - ) -{- -Discriminator adds a discriminator to each input value - -State: -prev_index: previous index -cur_discr: current discriminator - -Input: -data_in: input value -index: row index - -Output: -data_in: output value -discr: discriminator belonging to output value -new_discr: value of new discriminator, is -1 if cur_discr hasn't changed -index: Index belonging to the new discriminator --} -discriminator :: DiscrState -> (DataInt, ArrayIndex) -> - ( DiscrState - , ((DataInt, Discr), (Bit, ArrayIndex)) - ) -discriminator (State (prev_index,cur_discr)) (data_in, index) = - (State (prev_index', cur_discr'), ((data_in, discr),(new_discr, index))) +-- ======================================= +-- = System size configuration variables = +-- ======================================= +type DataSize = D64 +type IndexSize = D16 +type DiscrSize = D7 +type AdderDepth = D12 + +-- Derived configuration variables +type DiscrRange = Pow2 DiscrSize +type AdderDepthPL = AdderDepth :+: D3 + +-- ================= +-- = Type Aliasses = +-- ================= +type Shift = Index D2 +type DataInt = Signed DataSize +type ArrayIndex = Unsigned IndexSize +type Discr = Index DiscrRange +type OutputSignal = ((DataInt, ArrayIndex), Bool) + +-- ================================= +-- = Cell Definition and Accessors = +-- ================================= +type CellType = Bool +type Cell = (CellType, (DataInt, Discr)) + +valid :: Cell -> Bool +valid (x, _) = x + +value :: Cell -> DataInt +value (_, (v, _)) = v + +discr :: Cell -> Discr +discr (_, (_, d)) = d + +notValid :: Cell +notValid = (False, (0, 0)) + +-- ==================== +-- = Helper functions = +-- ==================== +v <<+ e = shiftIntoR v e +e +>> v = shiftIntoL v e + +-- ======================= +-- = Reducer State types = +-- ======================= +data DiscrRecord = + DiscrR { prev_index :: ArrayIndex + , cur_discr :: Unsigned DiscrSize + } +type DiscrState = State DiscrRecord + +type RippleState = + State (Vector (AdderDepthPL :+: D1) (CellType, Discr)) + +data BlockRecord = + Block { ptrs :: (Unsigned D4, Unsigned D4, Unsigned D4) + , buf1 :: MemState (AdderDepthPL :+: D1) DataInt + , buf2 :: MemState (AdderDepthPL :+: D1) DataInt + } +type BlockState = State BlockRecord + +type FpAdderState = + State ( ( (DataInt, DataInt, DataInt, DataInt) -- Buffer input and double buffer output of the FPAdder + , Vector AdderDepthPL (CellType, Discr) -- Validbits & discriminators of values in the FP pipeline + ) + , FpPlaceholder + ) + +type FpPlaceholder = + State (Vector AdderDepth DataInt) + +data OutputRecord = + Outp { valid_mem :: RAM DiscrRange CellType + , mem1 :: MemState DiscrRange DataInt + , mem2 :: MemState DiscrRange DataInt + , lutm :: MemState DiscrRange ArrayIndex + } +type OutputState = State OutputRecord + +data ReducerRecord = + Reducer { discrState :: DiscrState + , rippleState :: RippleState + , blockState :: BlockState + , pipeState :: FpAdderState + , resultState :: OutputState + , pipeline :: ( Vector AdderDepth (Discr, ArrayIndex, Bool) -- Buffer link between discriminator and Result buffer + , CellType -- Buffer Valid bit of the resultbuffer at T+1 + , Vector D2 (DataInt, ArrayIndex) -- Buffer Input (to encourage retiming) + , Vector D2 OutputSignal -- Buffer Output (to encourage retiming) + ) + } +type ReducerState = State ReducerRecord + +-- =========================================================== +-- = Discrimintor: Hands out new discriminator to the system = +-- =========================================================== +{-# ANN discriminator (InitState 'initDiscrState) #-} +discriminator :: + DiscrState -> + ArrayIndex -> + (DiscrState, Discr, Bool) +discriminator (State (DiscrR {..})) index = ( State DiscrR { prev_index = index + , cur_discr = cur_discr' + } + , discr + , new_discr + ) where - -- Update discriminator if index changes - cur_discr' | prev_index == index = cur_discr - | otherwise = cur_discr + 1 - -- Notify OutputBuffer if a new discriminator becomes in use - new_discr | prev_index == index = Low - | otherwise = High - prev_index' = index - discr = fromSizedWord cur_discr' - -{- -Second attempt at Fifo -Uses "write pointer"... ugly... -Can potentially be mapped to hardware - -State: -mem: content of the FIFO -wrptr: points to first free spot in the FIFO - -Input: -inp: (value,discriminator) pair -enable: Flushes 2 values from FIFO if 2, 1 value from FIFO if 1, no values - from FIFO if 0 - -Output -out1: ((value, discriminator),valid) pair of head FIFO -out2: ((value, discriminator),valid) pair of second register FIFO - -valid indicates if the output contains a valid discriminator --} -inputBuffer :: InputState -> - ((DataInt, Discr), RangedWord D2) -> - (InputState, ReducerSignal, ReducerSignal) -inputBuffer (State (mem,wrptr)) (inp,enable) = (State (mem',wrptr'),out1, out2) + new_discr = index /= prev_index + cur_discr' | new_discr = cur_discr + 1 + | otherwise = cur_discr + discr = fromUnsigned cur_discr' + +-- ====================================================== +-- = Input Buffer: Buffers incomming inputs when needed = +-- ====================================================== +{-# ANN rippleBuffer (InitState 'initRippleState) #-} +rippleBuffer :: + RippleState -> + (Discr, Shift) -> + (RippleState, (CellType, Discr), (CellType, Discr)) +rippleBuffer (State buf) (inp, shift) = (State buf', out1, out2) where - out1 = last mem -- output head of FIFO - out2 = last (init mem) -- output 2nd element - -- Update free spot pointer according to value of 'enable' - wrptr' | enable == 0 = wrptr - 1 - | enable == 1 = wrptr - | otherwise = wrptr + 1 - -- Write value to free spot - mem'' = replace mem wrptr (inp,High) - -- Flush values at head of fifo according to value of 'enable' - mem' | enable == 0 = mem'' - | enable == 1 = zero +> (init mem'') - | otherwise = zero +> (zero +> (init(init mem''))) - zero = (((0::DataInt),(0::Discr)),(Low::Bit)) - - -{- -floating point Adder - -output discriminator becomes discriminator of the first operant - -State: -state: "pipeline" of the fp Adder - -Input: -input1: out1 of the FIFO -input2: out2 of the FIFO -grant: grant signal comming from the controller, determines which value enters - the pipeline -mem_out: Value of the output buffer for the read address - Read address for the output buffer is the discriminator at the top of - the adder pipeline - -Output: -output: ((Value, discriminator),valid) pair at the top of the adder pipeline - -valid indicates if the output contains a valid discriminator --} -fpAdder :: FpAdderState -> - ( ReducerSignal - , ReducerSignal - , (RangedWord D2, RangedWord D2) - , ReducerSignal - ) -> - (FpAdderState, ReducerSignal) -fpAdder (State state) (input1, input2, grant, mem_out) = (State state', output) + -- Write value + next_valids = (map fst buf) <<+ True + buf'' = zipWith selects buf next_valids + selects cell next_valid = if (not (fst cell)) && next_valid then + (True, inp) + else + cell + -- Shift values + buf' | shift == 2 = (False, 0) +>> ((False, 0) +>> buf'') + | shift == 1 = (False, 0) +>> buf'' + | otherwise = buf'' + -- Read values + out1 = last buf + out2 = last (init buf) + +{-# ANN blockBuffer (InitState 'initBlockState) #-} +blockBuffer :: + BlockState -> + (DataInt, Shift) -> + (BlockState, DataInt, DataInt) +blockBuffer (State (Block {..})) (inp, shift) = ( State Block { ptrs = ptrs' + , buf1 = buf1' + , buf2 = buf2' + } + , out1, out2) + where + -- Do some state (un)packing + (rd_ptr1, rd_ptr2, wr_ptr) = ptrs + ptrs' = (rd_ptr1', rd_ptr2', wr_ptr') + -- Update pointers + count = fromIndex shift + (rd_ptr1', rd_ptr2') = (rd_ptr1 + count, rd_ptr2 + count) + wr_ptr' = wr_ptr + 1 + -- Write & Read from RAMs + (buf1', out1) = blockRAM buf1 inp (fromUnsigned rd_ptr1) (fromUnsigned wr_ptr) True + (buf2', out2) = blockRAM buf2 inp (fromUnsigned rd_ptr2) (fromUnsigned wr_ptr) True + +-- ============================================ +-- = Simulated pipelined floating point adder = +-- ============================================ +{-# ANN fpAdder (InitState 'initPipeState) #-} +fpAdder :: + FpAdderState -> + (Cell, Cell) -> + (FpAdderState, (Cell, Cell)) +fpAdder (State ((buffer, pipe), adderState)) (arg1, arg2) = (State ((buffer', pipe'), adderState'), (pipeT_1, pipeT)) where - -- output is head of the pipeline - output = last state - -- First value of 'grant' determines operant 1 - operant1 | (fst grant) == 0 = fst (fst (last state)) - | (fst grant) == 1 = fst (fst input2) - | otherwise = 0 - -- Second value of 'grant' determine operant 2 - operant2 | (snd grant) == 0 = fst (fst input1) - | (snd grant) == 1 = fst (fst mem_out) - | (otherwise) = 0 - -- Determine discriminator for new value - discr | (snd grant) == 0 = snd (fst input1) - | (snd grant) == 1 = snd (fst (last state)) - | otherwise = 0 - -- Determine if discriminator should be marked as valid - valid | grant == (2,2) = Low - | otherwise = High - -- Shift addition of the two operants into the pipeline - state' = (((operant1 + operant2),discr),valid) +> (init state) - -{- -Output logic - Determines when values are released from blockram to the output - -State: -mem: memory belonging to the blockRAM -lut: Lookup table that maps discriminators to Index' -valid: Lookup table for 'validity' of the content of the blockRAM - -Input: -discr: Value of the newest discriminator when it first enters the system. - (-1) otherwise. -index: Index belonging to the newest discriminator -data_in: value to be written to RAM -rdaddr: read address -wraddr: write address -wrenable: write enabled flag - -Output: -data_out: value of RAM at location 'rdaddr' -output: Reduced row when ready, (-1) otherwise --} -outputter :: OutputState -> - ( Discr - , ArrayIndex - , Bit - , DataInt - , Discr - , Discr - , Bit - ) -> - (OutputState, ReducerSignal, OutputSignal) -outputter (State (mem1, mem2, lut, valid)) - (discr, index, new_discr, data_in, rdaddr, wraddr, wrenable) = - ((State (mem1', mem2', lut', valid')), data_out, output) + -- Do some state (un)packing + (a1,a2,dataT_1,dataT) = buffer + buffer' = (value arg1, value arg2, adderOut, dataT_1) + -- placeholder adder + (adderState', adderOut) = fpPlaceholder adderState (a1, a2) + -- Save corresponding indexes and valid bits + pipe' = (valid arg1, discr arg1) +>> pipe + -- Produce output for time T and T+1 + pipeEndT = last pipe + pipeEndT_1 = last (init pipe) + pipeT = (fst pipeEndT, (dataT, snd pipeEndT)) + pipeT_1 = (fst pipeEndT_1,(dataT_1,snd pipeEndT_1)) + +{-# ANN fpPlaceholder (InitState 'initAdderState) #-} +fpPlaceholder :: FpPlaceholder -> (DataInt, DataInt) -> (FpPlaceholder, DataInt) +fpPlaceholder (State pipe) (arg1, arg2) = (State pipe', pipe_out) where - -- Lut is updated when new discriminator/index combination enters system - (lut', lut_out) = blockRAM lut index discr discr new_discr - -- Location becomes invalid when Reduced row leaves system - valid'' | (new_discr /= Low) && ((valid!discr) /= Low) = - replace valid discr Low - | otherwise = valid - -- Location becomes invalid when it is fed back into the pipeline - valid' | wrenable == Low = replace valid'' rdaddr Low - | otherwise = replace valid'' wraddr High - (mem1', mem_out1) = blockRAM mem1 data_in rdaddr wraddr wrenable - (mem2', mem_out2) = blockRAM mem2 data_in discr wraddr wrenable - data_out = ( ( (mem_out1) - , rdaddr - ) - , (valid!rdaddr) - ) - -- Reduced row is released when new discriminator enters system - -- And the position at the discriminator holds a valid value - output = ( ( (mem_out2) - , (lut_out) - ) - , (new_discr `hwand` (valid!discr)) - ) - -{- -Arbiter determines which rules are valid - -Input: -fp_out: output of the adder pipeline -mem_out: data_out of the output logic -inp1: Head of the input FIFO -inp2: Second element of input FIFO - -Output: -r4 - r0: vector of rules, rule is invalid if it's 0, valid otherwise --} -arbiter :: (ReducerSignal, ReducerSignal, ReducerSignal, ReducerSignal) -> - Vector D5 Bit -arbiter (fp_out, mem_out, inp1, inp2) = (r4 +> (r3 +> (r2 +> (r1 +> (singleton r0))))) - where -- unpack parameters - fp_valid = snd fp_out - next_valid = snd mem_out - inp1_valid = snd inp1 - inp2_valid = snd inp2 - fp_discr = snd (fst fp_out) - next_discr = snd (fst mem_out) - inp1_discr = snd (fst inp1) - inp2_discr = snd (fst inp2) - -- Apply rules - r0 | (fp_valid /= Low) && (next_valid /= Low) && (fp_discr == next_discr) - = High - | otherwise = Low - r1 | (fp_valid /= Low) && (inp1_valid /= Low) && (fp_discr == inp1_discr) - = High - | otherwise = Low - r2 | (inp1_valid /= Low) && (inp2_valid /= Low) && - (inp1_discr == inp2_discr) = High - | otherwise = Low - r3 | inp1_valid /= Low = High - | otherwise = Low - r4 = High - -{- -Controller determines which values are fed into the pipeline -and if the write enable flag for the Output RAM should be set -to true. Also determines how many values should be flushed from -the input FIFO. - -Input: -fp_out: output of the adder pipeline -mem_out: data_out of the output logic -inp1: Head of input FIFO -inp2: Second element of input FIFO - -Output: -grant: Signal that determines operants for the adder -enable: Number of values to be flushed from input buffer -wr_enable: Determine if value of the adder should be written to RAM --} -controller :: (ReducerSignal, ReducerSignal, ReducerSignal, ReducerSignal) -> - ((RangedWord D2, RangedWord D2), RangedWord D2, Bit) -controller (fp_out,mem_out,inp1,inp2) = (grant,enable,wr_enable) + pipe' = (arg1 + arg2) +> init pipe + pipe_out = last pipe + +-- =================================================== +-- = Optimized Partial Result Buffer, uses BlockRAMs = +-- =================================================== +{-# ANN resBuff (InitState 'initResultState) #-} +resBuff :: + OutputState -> + ( Cell, Cell, Bool, (Discr, ArrayIndex, Bool)) -> + (OutputState, Cell, OutputSignal) +resBuff (State (Outp {..})) (pipeT, pipeT_1, new_cell, (discrN, index, new_discr)) = ( State Outp { valid_mem = valid_mem' + , mem1 = mem1' + , mem2 = mem2' + , lutm = lutm' + } + , res_mem_out, output) where - -- Arbiter determines which rules are valid - valid = arbiter (fp_out,mem_out,inp1,inp2) - -- Determine which values should be fed to the adder - grant = if (valid!(4 :: RangedWord D4) == High) - then (0,1) - else if ((drop d3 valid) == $(vectorTH [High,Low])) - then (0,0) - else if ((drop d2 valid) == $(vectorTH [High,Low,Low])) - then (1,0) - else if ((drop d1 valid) == $(vectorTH [High,Low,Low,Low])) - then (2,0) - else (2,2) - -- Determine if some values should be flushed from input FIFO - enable = if (grant == (1,0)) - then 2 - else if ((grant == (0,0)) || (grant == (2,0))) - then 1 - else 0 - -- Determine if the output value of the adder should be written to RAM - wr_enable' = if (valid!(4 :: RangedWord D4) == High) - then Low - else if ((drop d3 valid) == $(vectorTH [High,Low])) - then Low - else if ((drop d2 valid) == $(vectorTH [High,Low,Low])) - then High - else if ((drop d1 valid) == $(vectorTH [High,Low,Low,Low])) - then High - else High - wr_enable = if ((snd fp_out) /= Low) then wr_enable' else Low - -{- -Reducer - -Combines all the earlier defined functions. Uses the second implementation -of the input FIFO. - -Parameter: -'n': specifies the max discriminator value. - -State: all the states of the used functions - -Input: (value,index) combination - -Output: reduced row --} + addrT = discr pipeT + addrT_1 = discr pipeT_1 + -- Purge completely reduced results from the system + clean_mem | new_discr = replace valid_mem discrN False + | otherwise = valid_mem + -- If a partial is fed back to the pipeline, make its location invalid + valid_mem' | new_cell = replace clean_mem addrT True + | otherwise = replace clean_mem addrT False + -- Two parrallel memories with the same write addr, but diff rdaddr for partial res and other for complete res + (mem1', partial) = blockRAM mem1 (value pipeT) addrT addrT new_cell + (mem2', complete) = blockRAM mem2 (value pipeT) discrN addrT new_cell + -- Lut maps discriminators to array index + (lutm', lut_out) = blockRAM lutm index discrN discrN new_discr + res_mem_out = (valid_mem!addrT_1, (partial,addrT)) + -- Output value to the system once a discriminator is reused + output = ((complete,lut_out), new_discr && (valid_mem!discrN)) + +-- ================================================================ +-- = Controller guides correct inputs to the floating point adder = +-- ================================================================ +controller :: + (Cell, Cell, Cell, Cell) -> + (Cell, Cell, Shift, Bool) +controller (inp1, inp2, pipeT, from_res_mem) = (arg1, arg2, shift, to_res_mem) + where + (arg1, arg2, shift, to_res_mem) + | valid pipeT && valid from_res_mem = (pipeT , from_res_mem , 0, False) + | valid pipeT && valid inp1 && discr pipeT == discr inp1 = (pipeT , inp1 , 1, False) + | valid inp1 && valid inp2 && discr inp1 == discr inp2 = (inp1 , inp2 , 2, valid pipeT) + | valid inp1 = (inp1 , (True, (0, discr inp1)) , 1, valid pipeT) + | otherwise = (notValid, notValid , 0, valid pipeT) + +-- ============================================= +-- = Reducer: Wrap up all the above components = +-- ============================================= {-# ANN reducer TopEntity #-} -reducer :: ReducerState -> - (DataInt, ArrayIndex) -> - (ReducerState, OutputSignal) -reducer (State (discrstate,inputstate,fpadderstate,outputstate)) input = - (State (discrstate',inputstate',fpadderstate',outputstate'),output) +{-# ANN reducer (InitState 'initReducerState) #-} +reducer :: + ReducerState -> + (DataInt, ArrayIndex) -> + (ReducerState, OutputSignal) +reducer (State (Reducer {..})) (data_in, index) = ( State Reducer { discrState = discrState' + , rippleState = rippleState' + , blockState = blockState' + , pipeState = pipeState' + , resultState = resultState' + , pipeline = pipeline' + } + , last outPipe) where - (discrstate', discr_out) = discriminator discrstate input - (inputstate',fifo_out1, fifo_out2) = inputBuffer inputstate ( - (fst discr_out), enable) - (fpadderstate', fp_out) = fpAdder fpadderstate (fifo_out1, - fifo_out2, grant, mem_out) - discr = snd (fst discr_out) - new_discr = fst (snd discr_out) - index = snd (snd discr_out) - rdaddr = snd (fst fp_out) - wraddr = rdaddr - data_in = fst (fst fp_out) - (outputstate', mem_out, output) = outputter outputstate (discr, - index, new_discr, data_in, rdaddr, - wraddr, wr_enable) - (grant,enable,wr_enable) = controller (fp_out, mem_out, - fifo_out1, fifo_out2) - - --- ------------------------------------------------------- --- -- Test Functions --- ------------------------------------------------------- --- --- "Default" Run function + -- Discriminator + (discrState' , discrN, new_discr) = discriminator discrState (snd (last inPipe)) + -- InputBuffer + (rippleState' , (inp1V, inp1I), (inp2V, inp2I)) = rippleBuffer rippleState (discrN, shift) + (blockState', inp1D, inp2D) = blockBuffer blockState ((fst (last inPipe)), shift) + (inp1,inp2) = ((inp1V,(inp1D,inp1I)),(inp2V,(inp2D,inp2I))) + -- FP Adder + (pipeState' , (pipeT_1, pipeT)) = fpAdder pipeState (arg1, arg2) + -- Result Buffer + (resultState', from_res_mem, output') = resBuff resultState (pipeT, pipeT_1, to_res_mem, last discrO) + -- Controller + (arg1,arg2,shift,to_res_mem) = controller (inp1, inp2, pipeT, (valT, snd from_res_mem)) + -- Optimizations/Pipelining + valT_1 | discr pipeT == discr pipeT_1 = not (valid from_res_mem) + | otherwise = valid from_res_mem + (discrO, valT, inPipe , outPipe) = pipeline + pipeline' = ( (discrN, index, new_discr) +>> discrO + , valT_1 + , (data_in, index) +>> inPipe + , output' +>> outPipe + ) + + +-- ======================== +-- = Initial State values = +-- ======================== +initDiscrState :: DiscrRecord +initDiscrState = DiscrR { prev_index = 255 + , cur_discr = 127 + } + +initRippleState :: Vector (AdderDepthPL :+: D1) (CellType, Discr) +initRippleState = copy (False, 0) + +initBlockState :: (Unsigned D4, Unsigned D4, Unsigned D4) +initBlockState = (0,1,0) + +initPipeState :: + ((DataInt,DataInt,DataInt,DataInt) + , Vector AdderDepthPL (CellType, Discr) + ) +initPipeState = ((0,0,0,0),copy (False, 0)) + +initAdderState :: Vector AdderDepth DataInt +initAdderState = copy 0 + +initResultState :: RAM DiscrRange CellType +initResultState = copy False + +initReducerState :: + ( Vector AdderDepth (Discr, ArrayIndex, Bool) + , CellType + , Vector D2 (DataInt, ArrayIndex) + , Vector D2 OutputSignal + ) +initReducerState = (copy (0, 0, False), False, copy (0,0), copy ((0,0), False)) + +initstate :: ReducerState +initstate = State ( Reducer { discrState = State initDiscrState + , rippleState = State initRippleState + , blockState = State Block { ptrs = initBlockState + , buf1 = State (copy 0) + , buf2 = State (copy 0) + } + , pipeState = State (initPipeState, State initAdderState) + , resultState = State Outp { valid_mem = initResultState + , mem1 = State (copy 0) + , mem2 = State (copy 0) + , lutm = State (copy 0) + } + , pipeline = initReducerState + }) + +-- ================== +-- = Test Functions = +-- ================== run func state [] = [] run func state (i:input) = o:out where (state', o) = func state i out = run func state' input --- --- -- "Special" Run function, also outputs new state --- run' func state [] = ([],[]) --- run' func state (i:input) = ((o:out), (state':ss)) --- where --- (state',o) = func state i --- (out,ss) = run' func state' input --- --- Run reducer + runReducer = ( reduceroutput , validoutput , equal + , allEqual ) where - input = siminput + -- input = randominput 900 7 + input = siminput istate = initstate output = run reducer istate input - reduceroutput = P.map fst (filter (\x -> (snd x) /= Low) output) + reduceroutput = P.map fst (P.filter (\x -> (snd x)) output) validoutput = [P.foldl (+) 0 - (P.map (\z -> toInteger (fst z)) - (filter (\x -> (snd x) == i) input)) | i <- [0..10]] - equal = [validoutput!!i == toInteger (fst (reduceroutput!!i)) | - i <- [0..10]] --- --- -- Generate infinite list of numbers between 1 and 'x' --- randX :: Integer -> [Integer] --- randX x = randomRs (1,x) (unsafePerformIO newStdGen) --- --- -- Generate random lists of indexes --- randindex 15 i = randindex 1 i --- randindex m i = (P.take n (repeat i)) P.++ (randindex (m+1) (i+1)) --- where --- [n] = P.take 1 rnd --- rnd = randomRs (1,m) (unsafePerformIO newStdGen) --- --- -- Combine indexes and values to generate random input for the reducer --- randominput n x = P.zip data_in index_in --- where --- data_in = P.map (fromInteger :: Integer -> DataInt) (P.take n (randX x)) --- index_in = P.map (fromInteger :: Integer -> ArrayIndex) --- (P.take n (randindex 7 0)) --- main = --- do --- putStrLn (show runReducer) - --- simulate f input s = do --- putStr "Input: " --- putStr $ show input --- putStr "\nInitial State: " --- putStr $ show s --- putStr "\n\n" --- foldl1 (>>) (map (printOutput) output) --- where --- output = run f input s - -initstate :: ReducerState -initstate = State - ( State ( (255 :: ArrayIndex) - , (7 :: SizedWord DiscrSize) - ) - , State ( copy ((0::DataInt,0::Discr),Low) - , (2 :: RangedWord AdderDepth) - ) - , State (copy ((0::DataInt,0::Discr),Low)) - , State ( State (copy (0::DataInt)) - , State (copy (0::DataInt)) - , State (copy (0::ArrayIndex)) - , (copy Low) - ) - ) + (P.map (\z -> P.toInteger (fst z)) + (P.filter (\x -> (snd x) == i) input)) | i <- [0..30]] + equal = [validoutput P.!! i == P.toInteger (fst (reduceroutput P.!! i)) | + i <- [0..30]] + allEqual = P.foldl1 (&&) equal -{-# ANN siminput TestInput #-} siminput :: [(DataInt, ArrayIndex)] -siminput = [(13,0)::(DataInt, ArrayIndex),(7,0)::(DataInt, ArrayIndex),(14,0)::(DataInt, ArrayIndex),(14,0)::(DataInt, ArrayIndex),(12,0)::(DataInt, ArrayIndex),(10,0)::(DataInt, ArrayIndex),(19,1)::(DataInt, ArrayIndex),(20,1)::(DataInt, ArrayIndex),(13,1)::(DataInt, ArrayIndex) - ,(5,1)::(DataInt, ArrayIndex),(9,1)::(DataInt, ArrayIndex),(16,1)::(DataInt, ArrayIndex),(15,1)::(DataInt, ArrayIndex),(10,2)::(DataInt, ArrayIndex),(13,2)::(DataInt, ArrayIndex),(3,2)::(DataInt, ArrayIndex),(9,2)::(DataInt, ArrayIndex),(19,2)::(DataInt, ArrayIndex),(5,3)::(DataInt, ArrayIndex) - ,(5,3)::(DataInt, ArrayIndex),(10,3)::(DataInt, ArrayIndex),(17,3)::(DataInt, ArrayIndex),(14,3)::(DataInt, ArrayIndex),(5,3)::(DataInt, ArrayIndex),(15,3)::(DataInt, ArrayIndex),(11,3)::(DataInt, ArrayIndex),(5,3)::(DataInt, ArrayIndex),(1,3)::(DataInt, ArrayIndex),(8,4)::(DataInt, ArrayIndex) - ,(20,4)::(DataInt, ArrayIndex),(8,4)::(DataInt, ArrayIndex),(1,4)::(DataInt, ArrayIndex),(11,4)::(DataInt, ArrayIndex),(10,4)::(DataInt, ArrayIndex),(13,5)::(DataInt, ArrayIndex),(18,5)::(DataInt, ArrayIndex),(5,5)::(DataInt, ArrayIndex),(6,5)::(DataInt, ArrayIndex),(6,5)::(DataInt, ArrayIndex) - ,(4,6)::(DataInt, ArrayIndex),(4,6)::(DataInt, ArrayIndex),(11,6)::(DataInt, ArrayIndex),(11,6)::(DataInt, ArrayIndex),(11,6)::(DataInt, ArrayIndex),(1,6)::(DataInt, ArrayIndex),(11,6)::(DataInt, ArrayIndex),(3,6)::(DataInt, ArrayIndex),(12,6)::(DataInt, ArrayIndex),(12,6)::(DataInt, ArrayIndex) - ,(2,6)::(DataInt, ArrayIndex),(14,6)::(DataInt, ArrayIndex),(11,7)::(DataInt, ArrayIndex),(13,7)::(DataInt, ArrayIndex),(17,7)::(DataInt, ArrayIndex),(9,7)::(DataInt, ArrayIndex),(19,8)::(DataInt, ArrayIndex),(4,9)::(DataInt, ArrayIndex),(18,10)::(DataInt, ArrayIndex) - ,(6,10)::(DataInt, ArrayIndex),(18,11)::(DataInt, ArrayIndex),(1,12)::(DataInt, ArrayIndex),(3,12)::(DataInt, ArrayIndex),(14,12)::(DataInt, ArrayIndex),(18,12)::(DataInt, ArrayIndex),(14,12)::(DataInt, ArrayIndex),(6,13)::(DataInt, ArrayIndex) - ,(9,13)::(DataInt, ArrayIndex),(11,14)::(DataInt, ArrayIndex),(4,14)::(DataInt, ArrayIndex),(1,14)::(DataInt, ArrayIndex),(14,14)::(DataInt, ArrayIndex),(14,14)::(DataInt, ArrayIndex),(6,14)::(DataInt, ArrayIndex),(11,15)::(DataInt, ArrayIndex) - ,(13,15)::(DataInt, ArrayIndex),(7,15)::(DataInt, ArrayIndex),(2,16)::(DataInt, ArrayIndex),(16,16)::(DataInt, ArrayIndex),(17,16)::(DataInt, ArrayIndex),(5,16)::(DataInt, ArrayIndex),(20,16)::(DataInt, ArrayIndex),(17,16)::(DataInt, ArrayIndex) - ,(14,16)::(DataInt, ArrayIndex),(18,17)::(DataInt, ArrayIndex),(13,17)::(DataInt, ArrayIndex),(1,17)::(DataInt, ArrayIndex),(19,18)::(DataInt, ArrayIndex),(1,18)::(DataInt, ArrayIndex),(20,18)::(DataInt, ArrayIndex),(4,18)::(DataInt, ArrayIndex) - ,(5,19)::(DataInt, ArrayIndex),(4,19)::(DataInt, ArrayIndex),(6,19)::(DataInt, ArrayIndex),(19,19)::(DataInt, ArrayIndex),(4,19)::(DataInt, ArrayIndex),(3,19)::(DataInt, ArrayIndex),(7,19)::(DataInt, ArrayIndex),(13,19)::(DataInt, ArrayIndex),(19,19)::(DataInt, ArrayIndex) - ,(8,19)::(DataInt, ArrayIndex) - ] +siminput = [(1,0),(5,1),(12,1),(4,2),(9,2),(2,2),(13,2),(2,2),(6,2),(1,2),(12,2),(13,3),(6,3),(11,3),(2,3),(11,3),(5,4),(11,4),(1,4),(7,4),(3,4),(4,4),(5,5),(8,5),(8,5),(13,5),(10,5),(7,5),(9,6),(9,6),(3,6),(11,6),(14,6),(13,6),(10,6),(4,7),(15,7),(13,7),(10,7),(10,7),(6,7),(15,7),(9,7),(1,7),(7,7),(15,7),(3,7),(13,7),(7,8),(3,9),(13,9),(2,10),(9,11),(10,11),(9,11),(2,11),(14,12),(14,12),(12,13),(7,13),(9,13),(7,14),(14,15),(5,16),(6,16),(14,16),(11,16),(5,16),(5,16),(7,17),(1,17),(13,17),(10,18),(15,18),(12,18),(14,19),(13,19),(2,19),(3,19),(14,19),(9,19),(11,19),(2,19),(2,20),(3,20),(13,20),(3,20),(1,20),(9,20),(10,20),(4,20),(8,21),(4,21),(8,21),(4,21),(13,21),(3,21),(7,21),(12,21),(7,21),(13,21),(3,21),(1,22),(13,23),(9,24),(14,24),(4,24),(13,25),(6,26),(12,26),(4,26),(15,26),(3,27),(6,27),(5,27),(6,27),(12,28),(2,28),(8,28),(5,29),(4,29),(1,29),(2,29),(9,29),(10,29),(4,30),(6,30),(14,30),(11,30),(15,31),(15,31),(2,31),(14,31),(9,32),(3,32),(4,32),(6,33),(15,33),(1,33),(15,33),(4,33),(3,33),(8,34),(12,34),(14,34),(15,34),(4,35),(4,35),(12,35),(14,35),(3,36),(14,37),(3,37),(1,38),(15,39),(13,39),(13,39),(1,39),(5,40),(10,40),(14,40),(1,41),(6,42),(8,42),(11,42),(11,43),(2,43),(11,43),(8,43),(12,43),(15,44),(14,44),(6,44),(8,44),(9,45),(5,45),(12,46),(6,46),(5,46),(4,46),(2,46),(9,47),(7,48),(1,48),(3,48),(10,48),(1,48),(6,48),(6,48),(11,48),(11,48),(8,48),(14,48),(5,48),(11,49),(1,49),(3,49),(11,49),(8,49),(3,50),(8,51),(9,52),(7,52),(7,53),(8,53),(10,53),(11,53),(14,54),(11,54),(4,54),(6,55),(11,55),(5,56),(7,56),(6,56),(2,56),(4,56),(12,56),(4,57),(12,57),(2,57),(14,57),(9,57),(12,57),(5,57),(11,57),(7,58),(14,58),(2,58),(10,58),(2,58),(14,58),(7,58),(12,58),(1,58),(11,59),(8,59),(2,59),(14,59),(6,59),(6,59),(6,59),(14,59),(4,59),(1,59),(4,60),(14,60),(6,60),(4,60),(8,60),(12,60),(1,60),(8,60),(8,60),(13,60),(10,61),(11,61),(6,61),(14,61),(10,61),(3,62),(10,62),(7,62),(14,62),(10,62),(4,62),(6,62),(1,62),(3,63),(3,63),(1,63),(1,63),(15,63),(7,64),(1,65),(4,65),(11,66),(3,66),(13,66),(2,67),(2,67),(5,68),(15,68),(11,68),(8,68),(4,69),(11,69),(12,69),(8,69),(7,70),(9,70),(6,70),(9,70),(11,70),(14,70),(5,71),(7,71),(11,72),(5,72),(3,72),(2,72),(1,73),(13,73),(9,73),(14,73),(5,73),(6,73),(14,73),(13,73),(3,74),(13,74),(3,75),(14,75),(10,75),(5,75),(3,75),(8,75),(9,76),(7,76),(10,76),(10,76),(8,77),(10,77),(11,77),(8,77),(2,77),(9,77),(9,77),(12,77),(4,77),(14,77),(10,77),(7,77),(3,77),(10,78),(8,79),(14,79),(11,80),(15,81),(6,81),(4,82),(6,82),(1,82),(12,83),(6,83),(11,83),(12,83),(15,83),(13,83),(1,84),(2,84),(11,84),(5,84),(2,84),(2,84),(3,84),(4,85),(6,86),(5,86),(15,86),(8,86),(9,86),(9,87),(9,87),(12,87),(4,87),(13,88),(14,88),(10,88),(11,88),(7,88),(4,88),(9,88),(1,88),(4,88),(4,88),(12,88),(8,89),(3,89),(10,89),(10,89),(5,89),(14,89),(11,89),(10,89),(5,90),(6,90),(10,90),(9,90),(8,90),(10,90),(5,90),(11,90),(6,90),(10,90),(7,90),(3,91),(7,91),(5,91),(15,91),(4,91),(6,91),(8,91),(1,91),(8,91),(12,92),(8,93),(9,93),(12,94),(8,94),(5,94),(11,95),(13,95),(5,96),(12,96),(8,96),(4,96),(7,97),(6,97),(4,97),(1,98),(5,98),(12,98),(13,99),(7,100),(12,100),(4,100),(10,100),(2,101),(3,101),(14,101),(12,101),(5,101),(2,101),(14,101),(15,101),(7,102),(13,102),(5,102),(7,102),(4,102),(8,102),(12,103),(15,103),(2,103),(2,103),(6,103),(6,103),(1,104),(14,104),(15,105),(3,105),(13,105),(1,105),(8,105),(8,105),(15,105),(13,105),(13,105),(6,105),(9,105),(6,106),(14,107),(12,107),(7,108),(7,108),(6,109),(11,109),(14,110),(8,111),(5,111),(15,111),(14,111),(3,111),(13,112),(12,112),(5,112),(10,112),(7,112),(5,113),(3,113),(2,113),(1,113),(15,113),(8,113),(10,113),(3,114),(6,114),(15,114),(4,115),(8,115),(1,115),(12,115),(5,115),(6,116),(2,116),(13,116),(12,116),(6,116),(10,117),(8,117),(14,118),(10,118),(3,118),(15,119),(6,119),(6,120),(5,121),(8,121),(4,122),(1,122),(9,123),(12,123),(6,124),(10,124),(2,124),(11,124),(9,125),(8,126),(10,126),(11,126),(14,126),(2,126),(5,126),(7,126),(3,127),(12,127),(15,128),(4,128),(1,129),(14,129),(8,129),(9,129),(6,129),(1,130),(11,130),(2,130),(13,130),(14,131),(2,131),(15,131),(4,131),(15,131),(8,131),(3,131),(8,132),(1,132),(13,132),(8,132),(5,132),(11,132),(14,132),(14,132),(4,132),(14,132),(5,132),(11,133),(1,133),(15,133),(8,133),(12,133),(8,134),(14,135),(11,136),(9,137),(3,137),(15,138),(1,138),(1,139),(4,139),(3,140),(10,140),(8,141),(12,141),(4,141),(12,141),(13,141),(10,141),(4,142),(6,142),(15,142),(4,142),(2,143),(14,143),(5,143),(10,143),(8,143),(9,143),(3,143),(11,143),(6,144),(3,145),(9,145),(10,145),(6,145),(11,145),(4,145),(13,145),(5,145),(4,145),(1,145),(3,145),(15,145),(14,146),(11,146),(9,146),(9,146),(10,146),(9,146),(3,146),(2,146),(10,146),(6,146),(7,146),(3,147),(4,147),(15,147),(11,147),(15,147),(1,147),(15,147),(14,147),(15,147),(5,147),(15,147),(4,147),(2,148),(12,149),(12,150),(10,150),(1,150),(7,151),(4,151),(14,151),(15,151),(5,152),(11,153),(3,153),(1,153),(1,153),(12,153),(1,154),(1,155),(11,155),(8,155),(3,155),(8,155),(8,155),(2,155),(9,156),(6,156),(12,156),(1,156),(3,156),(8,156),(5,157),(9,157),(12,157),(6,157),(8,158),(15,159),(2,159),(10,160),(10,160),(2,160),(6,160),(10,160),(8,160),(13,160),(12,161),(15,161),(14,161),(10,161),(13,161),(14,161),(3,161),(2,161),(1,161),(11,161),(7,161),(8,161),(4,162),(9,163),(3,164),(5,164),(9,164),(9,165),(7,165),(1,165),(6,166),(14,166),(3,166),(14,166),(4,166),(14,167),(5,167),(13,167),(12,167),(13,168),(9,168)]