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
", &(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
", &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
", 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
