[90ecade] | 1 | package main |
---|
| 2 | |
---|
| 3 | import ( |
---|
[2dd0689] | 4 | "context" |
---|
[90ecade] | 5 | "flag" |
---|
| 6 | "fmt" |
---|
| 7 | "math/rand" |
---|
| 8 | "os" |
---|
[aa1d13c] | 9 | "syscall" |
---|
[90ecade] | 10 | "sync/atomic" |
---|
| 11 | "time" |
---|
[2dd0689] | 12 | "unsafe" |
---|
| 13 | "golang.org/x/sync/semaphore" |
---|
[90ecade] | 14 | "golang.org/x/text/language" |
---|
| 15 | "golang.org/x/text/message" |
---|
| 16 | ) |
---|
| 17 | |
---|
[aa1d13c] | 18 | // ================================================== |
---|
| 19 | type MyData struct { |
---|
[3d19ae6] | 20 | _p1 [16]uint64 // padding |
---|
[aa1d13c] | 21 | ttid int |
---|
| 22 | id int |
---|
| 23 | data [] uint64 |
---|
[3d19ae6] | 24 | _p2 [16]uint64 // padding |
---|
[aa1d13c] | 25 | } |
---|
| 26 | |
---|
| 27 | func NewData(id int, size uint64) (*MyData) { |
---|
| 28 | var data [] uint64 |
---|
| 29 | data = make([]uint64, size) |
---|
| 30 | for i := uint64(0); i < size; i++ { |
---|
| 31 | data[i] = 0 |
---|
| 32 | } |
---|
[3d19ae6] | 33 | return &MyData{[16]uint64{0}, syscall.Gettid(), id, data,[16]uint64{0}} |
---|
[aa1d13c] | 34 | } |
---|
| 35 | |
---|
| 36 | func (this * MyData) moved( ttid int ) (uint64) { |
---|
| 37 | if this.ttid == ttid { |
---|
| 38 | return 0 |
---|
| 39 | } |
---|
| 40 | this.ttid = ttid |
---|
| 41 | return 1 |
---|
| 42 | } |
---|
| 43 | |
---|
| 44 | func (this * MyData) access( idx uint64 ) { |
---|
| 45 | this.data[idx % uint64(len(this.data))] += 1 |
---|
| 46 | } |
---|
| 47 | |
---|
| 48 | // ================================================== |
---|
| 49 | type MyCtx struct { |
---|
[3d19ae6] | 50 | _p1 [16]uint64 // padding |
---|
[2dd0689] | 51 | s * semaphore.Weighted |
---|
[34687d3] | 52 | d unsafe.Pointer |
---|
[024fa4b] | 53 | c context.Context |
---|
[aa1d13c] | 54 | ttid int |
---|
[34687d3] | 55 | id int |
---|
[3d19ae6] | 56 | _p2 [16]uint64 // padding |
---|
[2dd0689] | 57 | } |
---|
| 58 | |
---|
[c5a98f3] | 59 | func NewCtx( data * MyData, id int ) (MyCtx) { |
---|
[3d19ae6] | 60 | r := MyCtx{[16]uint64{0},semaphore.NewWeighted(1), unsafe.Pointer(data), context.Background(), syscall.Gettid(), id,[16]uint64{0}} |
---|
[c5a98f3] | 61 | r.s.Acquire(context.Background(), 1) |
---|
| 62 | return r |
---|
[aa1d13c] | 63 | } |
---|
| 64 | |
---|
| 65 | func (this * MyCtx) moved( ttid int ) (uint64) { |
---|
| 66 | if this.ttid == ttid { |
---|
| 67 | return 0 |
---|
| 68 | } |
---|
| 69 | this.ttid = ttid |
---|
| 70 | return 1 |
---|
| 71 | } |
---|
| 72 | |
---|
| 73 | // ================================================== |
---|
[c5a98f3] | 74 | // Atomic object where a single thread can wait |
---|
| 75 | // May exchanges data |
---|
[2dd0689] | 76 | type Spot struct { |
---|
[c5a98f3] | 77 | ptr uintptr // atomic variable use fo MES |
---|
| 78 | id int // id for debugging |
---|
[3d19ae6] | 79 | _p [16]uint64 // padding |
---|
[2dd0689] | 80 | } |
---|
| 81 | |
---|
[024fa4b] | 82 | // Main handshake of the code |
---|
| 83 | // Single seat, first thread arriving waits |
---|
| 84 | // Next threads unblocks current one and blocks in its place |
---|
| 85 | // if share == true, exchange data in the process |
---|
[aa1d13c] | 86 | func (this * Spot) put( ctx * MyCtx, data * MyData, share bool) (* MyData, bool) { |
---|
[024fa4b] | 87 | new := uintptr(unsafe.Pointer(ctx)) |
---|
[8235415] | 88 | // old_d := ctx.d |
---|
[c5a98f3] | 89 | |
---|
| 90 | // Attempt to CAS our context into the seat |
---|
[2dd0689] | 91 | var raw uintptr |
---|
| 92 | for true { |
---|
| 93 | raw = this.ptr |
---|
[c5a98f3] | 94 | if raw == uintptr(1) { // Seat is closed, return |
---|
[34687d3] | 95 | return nil, true |
---|
[2dd0689] | 96 | } |
---|
[024fa4b] | 97 | if atomic.CompareAndSwapUintptr(&this.ptr, raw, new) { |
---|
[c5a98f3] | 98 | break // We got the seat |
---|
[2dd0689] | 99 | } |
---|
[90ecade] | 100 | } |
---|
| 101 | |
---|
[c5a98f3] | 102 | // If we aren't the fist in, wake someone |
---|
[2dd0689] | 103 | if raw != uintptr(0) { |
---|
[aa1d13c] | 104 | var val *MyCtx |
---|
| 105 | val = (*MyCtx)(unsafe.Pointer(raw)) |
---|
[c5a98f3] | 106 | |
---|
| 107 | // If we are sharing, give them our data |
---|
[90ecade] | 108 | if share { |
---|
[34687d3] | 109 | // fmt.Printf("[%d] - %d update %d: %p -> %p\n", this.id, ctx.id, val.id, val.d, data) |
---|
| 110 | atomic.StorePointer(&val.d, unsafe.Pointer(data)) |
---|
[90ecade] | 111 | } |
---|
[2dd0689] | 112 | |
---|
[c5a98f3] | 113 | // Wake them up |
---|
[34687d3] | 114 | // fmt.Printf("[%d] - %d release %d\n", this.id, ctx.id, val.id) |
---|
[2dd0689] | 115 | val.s.Release(1) |
---|
| 116 | } |
---|
| 117 | |
---|
[34687d3] | 118 | // fmt.Printf("[%d] - %d enter\n", this.id, ctx.id) |
---|
[c5a98f3] | 119 | |
---|
| 120 | // Block once on the seat |
---|
[024fa4b] | 121 | ctx.s.Acquire(ctx.c, 1) |
---|
[c5a98f3] | 122 | |
---|
| 123 | // Someone woke us up, get the new data |
---|
[aa1d13c] | 124 | ret := (* MyData)(atomic.LoadPointer(&ctx.d)) |
---|
[34687d3] | 125 | // fmt.Printf("[%d] - %d leave: %p -> %p\n", this.id, ctx.id, ret, old_d) |
---|
| 126 | |
---|
| 127 | return ret, false |
---|
[2dd0689] | 128 | } |
---|
| 129 | |
---|
[c5a98f3] | 130 | // Shutdown the spot |
---|
| 131 | // Wake current thread and mark seat as closed |
---|
[2dd0689] | 132 | func (this * Spot) release() { |
---|
[aa1d13c] | 133 | val := (*MyCtx)(unsafe.Pointer(atomic.SwapUintptr(&this.ptr, uintptr(1)))) |
---|
[2dd0689] | 134 | if val == nil { |
---|
| 135 | return |
---|
[90ecade] | 136 | } |
---|
[2dd0689] | 137 | |
---|
[c5a98f3] | 138 | // Someone was there, release them |
---|
[2dd0689] | 139 | val.s.Release(1) |
---|
[90ecade] | 140 | } |
---|
| 141 | |
---|
[aa1d13c] | 142 | // ================================================== |
---|
[c5a98f3] | 143 | // Struct for result, Go doesn't support passing tuple in channels |
---|
[aa1d13c] | 144 | type Result struct { |
---|
| 145 | count uint64 |
---|
| 146 | gmigs uint64 |
---|
| 147 | dmigs uint64 |
---|
| 148 | } |
---|
| 149 | |
---|
| 150 | func NewResult() (Result) { |
---|
| 151 | return Result{0, 0, 0} |
---|
| 152 | } |
---|
| 153 | |
---|
| 154 | // ================================================== |
---|
[c5a98f3] | 155 | // Random number generator, Go's native one is to slow and global |
---|
[fd84538] | 156 | func __xorshift64( state * uint64 ) (uint64) { |
---|
| 157 | x := *state |
---|
| 158 | x ^= x << 13 |
---|
| 159 | x ^= x >> 7 |
---|
| 160 | x ^= x << 17 |
---|
| 161 | *state = x |
---|
| 162 | return x |
---|
| 163 | } |
---|
[2dd0689] | 164 | |
---|
[c5a98f3] | 165 | // ================================================== |
---|
| 166 | // Do some work by accessing 'cnt' cells in the array |
---|
[aa1d13c] | 167 | func work(data * MyData, cnt uint64, state * uint64) { |
---|
[94d93510] | 168 | for i := uint64(0); i < cnt; i++ { |
---|
[aa1d13c] | 169 | data.access(__xorshift64(state)) |
---|
[94d93510] | 170 | } |
---|
| 171 | } |
---|
| 172 | |
---|
[c5a98f3] | 173 | // Main body of the threads |
---|
[aa1d13c] | 174 | func local(result chan Result, start chan struct{}, size uint64, cnt uint64, channels [] Spot, share bool, id int) { |
---|
[c5a98f3] | 175 | // Initialize some data |
---|
| 176 | state := rand.Uint64() // RNG state |
---|
| 177 | data := NewData(id, size) // Starting piece of data |
---|
| 178 | ctx := NewCtx(data, id) // Goroutine local context |
---|
[2dd0689] | 179 | |
---|
[c5a98f3] | 180 | // Prepare results |
---|
[aa1d13c] | 181 | r := NewResult() |
---|
[c5a98f3] | 182 | |
---|
| 183 | // Wait for start |
---|
[90ecade] | 184 | <- start |
---|
[c5a98f3] | 185 | |
---|
| 186 | // Main loop |
---|
[90ecade] | 187 | for true { |
---|
[c5a98f3] | 188 | // Touch our current data, write to invalidate remote cache lines |
---|
[aa1d13c] | 189 | work(data, cnt, &state) |
---|
[90ecade] | 190 | |
---|
[c5a98f3] | 191 | // Wait on a random spot |
---|
[fd84538] | 192 | i := __xorshift64(&state) % uint64(len(channels)) |
---|
[34687d3] | 193 | var closed bool |
---|
| 194 | data, closed = channels[i].put(&ctx, data, share) |
---|
[90ecade] | 195 | |
---|
[c5a98f3] | 196 | // Check if the experiment is over |
---|
| 197 | if closed { break } // yes, spot was closed |
---|
| 198 | if clock_mode && atomic.LoadInt32(&stop) == 1 { break } // yes, time's up |
---|
| 199 | if !clock_mode && r.count >= stop_count { break } // yes, iterations reached |
---|
[aa1d13c] | 200 | |
---|
[c5a98f3] | 201 | // Check everything is consistent |
---|
| 202 | if uint64(len(data.data)) != size { panic("Data has weird size") } |
---|
| 203 | |
---|
| 204 | // write down progress and check migrations |
---|
[aa1d13c] | 205 | ttid := syscall.Gettid() |
---|
| 206 | r.count += 1 |
---|
| 207 | r.gmigs += ctx .moved(ttid) |
---|
| 208 | r.dmigs += data.moved(ttid) |
---|
[90ecade] | 209 | } |
---|
| 210 | |
---|
[c5a98f3] | 211 | // Mark goroutine as done |
---|
[90ecade] | 212 | atomic.AddInt64(&threads_left, -1); |
---|
[c5a98f3] | 213 | |
---|
| 214 | // return result |
---|
[aa1d13c] | 215 | result <- r |
---|
[90ecade] | 216 | } |
---|
| 217 | |
---|
[c5a98f3] | 218 | // ================================================== |
---|
| 219 | // Program main |
---|
[90ecade] | 220 | func main() { |
---|
[c5a98f3] | 221 | // Benchmark specific command line arguments |
---|
[f4f79dd] | 222 | work_sizeOpt := flag.Uint64("w", 2 , "Size of the array for each threads, in words (64bit)") |
---|
| 223 | countOpt := flag.Uint64("c", 2 , "Number of words to touch when working (random pick, cells can be picked more than once)") |
---|
[90ecade] | 224 | shareOpt := flag.Bool ("s", false, "Pass the work data to the next thread when blocking") |
---|
| 225 | |
---|
[c5a98f3] | 226 | // General benchmark initialization and deinitialization |
---|
[2dd0689] | 227 | defer bench_init()() |
---|
[90ecade] | 228 | |
---|
[c5a98f3] | 229 | // Eval command line arguments |
---|
[90ecade] | 230 | size := *work_sizeOpt |
---|
| 231 | cnt := *countOpt |
---|
| 232 | share := *shareOpt |
---|
| 233 | |
---|
[c5a98f3] | 234 | // Check params |
---|
[90ecade] | 235 | if ! (nthreads > nprocs) { |
---|
| 236 | fmt.Fprintf(os.Stderr, "Must have more threads than procs\n") |
---|
| 237 | os.Exit(1) |
---|
| 238 | } |
---|
| 239 | |
---|
[c5a98f3] | 240 | // Make global data |
---|
| 241 | barrierStart := make(chan struct{}) // Barrier used at the start |
---|
| 242 | threads_left = int64(nprocs) // Counter for active threads (not 'nthreads' because at all times 'nthreads - nprocs' are blocked) |
---|
| 243 | result := make(chan Result) // Channel for results |
---|
| 244 | channels := make([]Spot, nthreads - nprocs) // Number of spots |
---|
[90ecade] | 245 | for i := range channels { |
---|
[3d19ae6] | 246 | channels[i] = Spot{uintptr(0), i,[16]uint64{0}} // init spots |
---|
[90ecade] | 247 | } |
---|
| 248 | |
---|
[c5a98f3] | 249 | // start the goroutines |
---|
[90ecade] | 250 | for i := 0; i < nthreads; i++ { |
---|
[34687d3] | 251 | go local(result, barrierStart, size, cnt, channels, share, i) |
---|
[90ecade] | 252 | } |
---|
| 253 | fmt.Printf("Starting\n"); |
---|
| 254 | |
---|
[2dd0689] | 255 | atomic.StoreInt32(&stop, 0) |
---|
[90ecade] | 256 | start := time.Now() |
---|
[c5a98f3] | 257 | close(barrierStart) // release barrier |
---|
[90ecade] | 258 | |
---|
[c5a98f3] | 259 | wait(start, true); // general benchmark wait |
---|
[90ecade] | 260 | |
---|
[2dd0689] | 261 | atomic.StoreInt32(&stop, 1) |
---|
[90ecade] | 262 | end := time.Now() |
---|
| 263 | delta := end.Sub(start) |
---|
| 264 | |
---|
| 265 | fmt.Printf("\nDone\n") |
---|
| 266 | |
---|
[c5a98f3] | 267 | // release all the blocked threads |
---|
[2dd0689] | 268 | for i := range channels { |
---|
| 269 | channels[i].release() |
---|
| 270 | } |
---|
| 271 | |
---|
[c5a98f3] | 272 | // Join and accumulate results |
---|
[f4f79dd] | 273 | results := NewResult() |
---|
[90ecade] | 274 | for i := 0; i < nthreads; i++ { |
---|
[024fa4b] | 275 | r := <- result |
---|
[f4f79dd] | 276 | results.count += r.count |
---|
| 277 | results.gmigs += r.gmigs |
---|
| 278 | results.dmigs += r.dmigs |
---|
[90ecade] | 279 | } |
---|
| 280 | |
---|
[c5a98f3] | 281 | // Print with nice 's, i.e. 1'000'000 instead of 1000000 |
---|
[90ecade] | 282 | p := message.NewPrinter(language.English) |
---|
| 283 | p.Printf("Duration (ms) : %f\n", delta.Seconds()); |
---|
| 284 | p.Printf("Number of processors : %d\n", nprocs); |
---|
| 285 | p.Printf("Number of threads : %d\n", nthreads); |
---|
| 286 | p.Printf("Work size (64bit words): %d\n", size); |
---|
[f4f79dd] | 287 | p.Printf("Total Operations(ops) : %15d\n", results.count) |
---|
| 288 | p.Printf("Total G Migrations : %15d\n", results.gmigs) |
---|
| 289 | p.Printf("Total D Migrations : %15d\n", results.dmigs) |
---|
| 290 | p.Printf("Ops per second : %18.2f\n", float64(results.count) / delta.Seconds()) |
---|
| 291 | p.Printf("ns per ops : %18.2f\n", float64(delta.Nanoseconds()) / float64(results.count)) |
---|
| 292 | p.Printf("Ops per threads : %15d\n", results.count / uint64(nthreads)) |
---|
| 293 | p.Printf("Ops per procs : %15d\n", results.count / uint64(nprocs)) |
---|
| 294 | p.Printf("Ops/sec/procs : %18.2f\n", (float64(results.count) / float64(nprocs)) / delta.Seconds()) |
---|
| 295 | p.Printf("ns per ops/procs : %18.2f\n", float64(delta.Nanoseconds()) / (float64(results.count) / float64(nprocs))) |
---|
[90ecade] | 296 | } |
---|