From mboxrd@z Thu Jan  1 00:00:00 1970
Mime-Version: 1.0 (Apple Message framework v622)
In-Reply-To: <90a144662276bb4fdcc4312728a1d643@orthanc.cc.titech.ac.jp>
References: <90a144662276bb4fdcc4312728a1d643@orthanc.cc.titech.ac.jp>
Content-Type: text/plain; charset=US-ASCII; format=flowed
Message-Id: <4345520b4d36884e162c8862b90fc2f9@ar.aichi-u.ac.jp>
Content-Transfer-Encoding: 7bit
From: arisawa@ar.aichi-u.ac.jp
Subject: Re: [9fans] run and mount
Date: Tue,  2 Aug 2005 03:29:57 +0900
To: Fans of the OS Plan 9 from Bell Labs <9fans@cse.psu.edu>
Topicbox-Message-UUID: 724f644c-ead0-11e9-9d60-3106f5b1d025


> As a matter of fact, I'm going to ask 9fans to volunteer
> cpu seconds to compute 25 queen problem using this. :)

You can estimate for computing power to do this.

The task to get solution of N-queens problem can be divided
into small independent pieces of tasks.
We can get Open-MP style program qn24b-version1/omp
from http://www.yuba.is.uec.ac.jp/~kis/nq/index.htm

I transformed this program so that we can execute such like
         queen n i:j
this means n-queens problem of task(piece) range i to j
(You can get this program in co.aichi-u.ac.jp using cpu command
and look /usr/arisawa/src/taskfs/Q/src/)

I measured the time
	time queen n 0:1
0:1 means the first one piece.

The result measured on 2.4GHz Xeon
         n       time    # of pieces
         21      5s       41176
         22      33s     49480
         23      238s    64072
         24      1751s   75516
         25      13590s  95472
note that the time required to compute one piece increases rapidly

-bash$ python
Python 2.3 (#1, Sep 13 2003, 00:49:11)
[GCC 3.3 20030304 (Apple Computer, Inc. build 1495)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
 >>> 13590*95472
1297464480
 >>> 1297464480/(60*60*24*365)
41
 >>>

41 years on single computer!
500 volunteers who can offer one month?
I want rather 2000 9grid computers...

Kenji Arisawa