Friday, June 20, 2008

Multi-Core Ant Colony Optimization for TSP in Scala

I've added a new page Multi-Core Ant Colony Optimization for TSP in Scala.

Scala is a hybrid functional and object-oriented programming language. It is based on the Java JVM, so it has available Just-in-Time (JIT) native compilation and native thread support. It has access to the wide variety of class libraries available for Java.

Like Erlang, Scala supports an Actor-style message-passing concurrency model. More traditional thread-based concurrency with locks and shared memory is also available. Unlike Erlang and Haskell, Scala values are not immutable. Like SML and Haskell, typing is static with type inference.



Erlang and Alice SML omitted from graph. Note change from previous tests: 1000 interations, instead of 100. Still 200 cities.

Cores Erlang Haskell Scala OCaml MLton Alice
SML SML
1 372 86 41.6 6.0 676
2 192 63
3 141 58
4 98 54 14.6 1.6

All times in seconds.

If anyone knows how to reduce the number of cores used by the JVM, I'll fill in the rest of the table for Scala.

4 comments:

Daniel Spiewak said...

You would probably get slightly better performance out of Scala if you used event-based actors, rather than forcing threads. I'm sort of surprised that your single-core test wasn't slower, since you're actually forcing a minimum of two separate threads between the actors.

Eric Rollins said...

I don't think the single-core scala test is using (extra) threads.

if (isSerial) {
println("running serial")

i = 0

while (i < ants.length) {
ants(i).act
i += 1
}

In this case I never call ants(i).start, so multiple threads should not be created. I'm simply sequentially running the act methods embedded in the AntActor objects. The CPU traces don't appear to show more than one core active during the "serial" run. And note the ResultGatherer is never created in this case.

Daniel Spiewak said...

Hmm. Well, if your tests show only one thread then obviously I'm wrong. :-) I haven't been able to play with actors as much as I would like, so you've probably got a lot more knowledge on them than I have.

WadeMealing said...

I dont know much java, but if you are using Linux you can reduce it OS side with the kernel parameter maxcpus=NUMBER.