GoLang program executing on single thread even with GOMAXPROCS(4)

Issue

In the following GoLang program, I am trying to implement the stable marriage problem for N men and N women, using 2*N goroutines (1 for each man and woman).

The program closely follows the program definition as each goroutine (read “each man”) sends a message via channel to the desired woman goroutine who in turn rejects/accepts his proposal. I expected the program to easily be scheduled on multiple threads on setting runtime.GOMAXPROCS(4) however it still runs in (almost) the exact same time (and running linux command time still shows CPU usage at 100% instead of expected 400%)

package main

import (
    "fmt"
    "runtime"
    "time"
)

const N = 500

type human struct {
    pref    [N]int
    phone   chan int
    cur_eng int
    cur_num int
    id      int
}

var men = [N]human{}
var women = [N]human{}

func man(id int) {
    guy := &men[id]
    for {
        runtime.Gosched()
        for j := guy.cur_num + 1; j < N; j++ {
            guy.cur_num = j
            girl := &women[guy.pref[guy.cur_num]]
            girl.phone <- guy.id
            msg := <-guy.phone
            if msg == 1 {
                guy.cur_eng = guy.pref[guy.cur_num]
                break
            }
        }
        select {
        case <-guy.phone:
            guy.cur_eng = -1
        }
    }
}

func woman(id int, termi chan bool) {
    girl := &women[id]
    for {

        runtime.Gosched()
        select {
        case msg := <-girl.phone:
            if msg >= 0 {
                if girl.cur_eng == -1 {
                    men[msg].phone <- 1
                    girl.cur_eng = msg
                    termi <- true
                } else if girl.pref[girl.cur_eng] < girl.pref[msg] {
                    men[msg].phone <- 0
                } else {
                    men[msg].phone <- 1
                    men[girl.cur_eng].phone <- -10
                    girl.cur_eng = msg
                }
            }
        }
    }
}

func main() {
    runtime.GOMAXPROCS(8)
    for i := 0; i < N; i++ {
        men[i] = human{pref: [N]int{}, phone: make(chan int), cur_eng: -1, cur_num: -1, id: i}
        for j := 0; j < N; j++ {
            fmt.Scanf("%d\n", &(men[i].pref[j]))
        }
    }
    for i := 0; i < N; i++ {
        women[i] = human{pref: [N]int{}, phone: make(chan int), cur_eng: -1, cur_num: -1, id: i}
        for j := 0; j < N; j++ {
            t := 0
            fmt.Scanf("%d\n", &t)
            women[i].pref[t] = j
        }
    }
    termi := make(chan bool)
    for i := 0; i < N; i++ {
        go man(i)
        go woman(i, termi)
    }
    for i := 0; i < N; i++ {
        <-termi
    }
    time.Sleep(100 * time.Millisecond)
    for i := 0; i < N; i++ {
        fmt.Printf("%d %d\n", i, men[i].cur_eng)
    }
}

EDIT: The serial implementation of the program I made is here. The time comparison shows both running in almost identical time (1.27s for serial, 1.30s for above one).

Also, the algorithm followed for the parallel implementation was made according to this as well as I could understand (I used goroutines as I didn’t know how to use MPI).
Please feel free to suggest an alternative implementation (parallel) if possible.

The program above needs the following as input file : https://drive.google.com/file/d/0B6jsnt965ZwrWlV1OE9LLVA1LUk/view?usp=sharing

Solution

I think the input file you provided would take that much time to be read by the program(via scanf per line).

Answered By – Vinayak Tantia

Answer Checked By – Willingham (GoLangFix Volunteer)

Leave a Reply

Your email address will not be published.