Sequential.hs 4.24 KB
Newer Older
1 2 3
--
-- orbit-int sequential implementation
--
4 5 6
module Sequential( -- Types
                   Generator
                   -- Functions
Yiannis Tsiouris's avatar
Yiannis Tsiouris committed
7 8
                 , orbit
                 ) where
9

10 11
import           Data.Dequeue  (BankersDequeue, fromList, popFront, pushBack)
import           Data.Hashable (hash)
12

13 14
import           Table         (Freq, Vertex, VTable, freq_to_stat, get_freq,
                                insert, is_member, new, to_list)
15 16
import           Utils         (Generator, now)

17
type SeqConf = ([Generator], Int)
18
type SeqStats = [(String, String)]
19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

-- DATA
--   Static Machine Configuration:
--     {Gs,               --list of generators
--      TableSize}        --hash table size (ie. #slots)
--
--   Statistics:
--     List of pairs where the first component is an atom, the second
--     some data. Part of the data is the fill frequency of the table
--     (a list whose ith element indicates frequency of filling degree i).

-- compute orbit of elements in list Xs under list of generators Gs,
-- where the hash table is of size TableSize.
-- The function returns a pair consisting of the computed orbit and a singleton
-- list of statistics (mainly runtime and fill degree of the table).
34
orbit :: [Generator] -> [Vertex] -> Int -> ([Vertex],  [SeqStats])
35
orbit gs xs tableSize = (to_list finalTable, [stat])
36 37
  where -- assemble static configuration
        staticMachConf = mk_static_mach_conf gs tableSize
38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54
        -- initialise hash table and work queue
        table = new tableSize
        queue = fromList xs
        -- start wall clock timer
        startTime = now
        -- start vertex server and compute orbit
        (finalTable, vertsRecvd) = vertex_server staticMachConf table queue 0
        -- measure elapsed time (in milliseconds)
        elapsedTime = now - startTime
        -- return result
        stat = seq_stats elapsedTime (get_freq finalTable) vertsRecvd

-- main loop working off work Queue;
-- StaticMachConf -- static data
-- Table          -- hash table holding vertices
-- Queue          -- work queue
-- VertsRecvd     -- number of vertices removed from the Queue so far
55 56
vertex_server :: SeqConf -> VTable -> BankersDequeue Vertex -> Int
                 -> (VTable, Int)
57
vertex_server staticMachConf table queue vertsRecvd =
58 59 60 61 62
    case popFront queue of
        (Nothing, _)     -> (table, vertsRecvd)
        (Just x, queue1) ->
            let (newTable, newQueue) = handle_vertex staticMachConf x table queue1
            in vertex_server staticMachConf newTable newQueue (vertsRecvd + 1)
63 64 65 66

-- handle_vertex checks whether vertex X is stored in Table;
-- if not, it is in inserted and the images of the generators
-- are pushed into the work queue.
67 68
handle_vertex :: SeqConf -> Vertex -> VTable -> BankersDequeue Vertex
                 -> (VTable, BankersDequeue Vertex)
69
handle_vertex staticMachConf x table queue =
70 71 72 73 74 75 76 77 78 79 80 81
    case is_member x slot table of                -- check whether X is already in Table
        -- X already in table; do nothing
        True  -> (table, queue)
        -- X not in table
        False ->
            let -- insert X at Slot
                newTable = insert x slot table
                -- compute images of X under generators Gs and enqueue
                xs = [g x | g <- get_gens staticMachConf]
                newQueue = foldl pushBack queue xs
            in (newTable, newQueue) -- return updated table and queue
  where slot = hash_vertex staticMachConf x -- compute Slot
82 83

-- hash_vertex computes the hash table slot of vertex X
84
hash_vertex :: SeqConf -> Vertex -> Int
85
hash_vertex staticMachConf x = hsh `rem` tableSize
86 87 88 89 90 91 92
  where tableSize = get_table_size staticMachConf
        hsh = abs $ hash x

-------------------------------------------------------------------------------
-- auxiliary functions

-- functions operating on the StaticMachConf
93
mk_static_mach_conf :: [Generator] -> Int -> SeqConf
94 95
mk_static_mach_conf gs tableSize = (gs, tableSize)

96
get_gens :: SeqConf -> [Generator]
97 98
get_gens staticMachConf = fst staticMachConf

99
get_table_size :: SeqConf -> Int
100 101 102
get_table_size staticMachConf = snd staticMachConf

-- produce readable statistics
103
seq_stats :: Int -> Freq -> Int -> SeqStats
104
seq_stats elapsedTime frequency vertsRecvd =
105 106 107
      ("wall_time", show elapsedTime)
    : ("vertices_recvd", show vertsRecvd)
    : freq_to_stat frequency