[r-t] Exhausted search spaces

Sat Feb 6 14:51:03 UTC 2010


 

 

 

 

> From: ringing-theory-request at bellringers.net
> Subject: ringing-theory Digest, Vol 65, Issue 8
> To: ringing-theory at bellringers.net
> Date: Sat, 6 Feb 2010 12:00:02 +0000
> 
> Send ringing-theory mailing list submissions to
> ringing-theory at bellringers.net
> 
> To subscribe or unsubscribe via the World Wide Web, visit
> http://bellringers.net/mailman/listinfo/ringing-theory_bellringers.net
> 
> or, via email, send a message with subject or body 'help' to
> ringing-theory-request at bellringers.net
> 
> You can reach the person managing the list at
> ringing-theory-owner at bellringers.net
> 
> When replying, please edit your Subject line so it is more specific
> than "Re: Contents of ringing-theory digest..."
> 
> 
> Today's Topics:
> 
> 1. Re: Exhausted search spaces (Mark Davies)
> 2. Parallel searches [was Exhausted search spaces] (Mark Davies)
> 3. Re: Parallel searches [was Exhausted search spaces] (Graham John)
> 4. Re: Parallel searches [was Exhausted search spaces] (Mark Davies)
> 5. Re: Exhausted search spaces (Simon Humphrey)
> 6. Re: Exhausted search spaces (Graham John)
> 7. Hyperthreading [was Exhausted search spaces] (Mark Davies)
> 
> 
> ----------------------------------------------------------------------
> 
> Message: 1
> Date: Fri, 05 Feb 2010 17:11:52 +0000
> From: Mark Davies <mark at snowtiger.net>
> To: ringing-theory at bellringers.net
> Subject: Re: [r-t] Exhausted search spaces
> Message-ID: <4B6C5158.1080701 at snowtiger.net>
> Content-Type: text/plain; charset=ISO-8859-1; format=flowed
> 
> Simon Humphrey writes,
> 
> > Surely you don't have a 6 GHz processor, Mark? I thought 3.0 Ghz is
> > still about the limit for processor speed/ Modern technology is only
> > able to provide more computing power by squeezing multiple processors
> > onto the same chip, but that won't speed up single-threaded
> > applications.
> 
> No, my current machine is a 2.8GHz i7 quad-core, and (for SMC32) it's 
> only barely as fast as my previous box, an Athlon X2 4200.
> 
> I don't know why your PC is performing so badly on the SMC32 benchmark. 
> Possibly your L2 or L3 caches aren't up to scratch, or maybe disabling 
> hyperthreading has made it worse. I'm not quite sure why you've done 
> that, as I don't think it'll give you any benefits! I could be wrong, 
> but I certainly wouldn't expect it to help SMC32.
> 
> In terms of I/O, yes in theory that can be a bottleneck. In practice, 
> even if you're producing a composition every 30 microseconds, there is 
> much more work to do in the search phase than there is in the output 
> phase. The number of bytes output for each composition is small, and the 
> disk writes are buffered. Given the above, the CPU should never be 
> waiting on I/O on a normal search.
> 
> Computers and their associated numbers never cease to amaze me, after 
> all these years. We still sit around waiting for busy cursors for 
> minutes on end, cursing how slow they are - yet with a decent bit of 
> code they can search for, prove and output a composition in a few 
> microseconds. A microsecond is really too short a time for the human 
> brain to properly imagine, but it is actually a vast aeon for a modern 
> CPU. You can carry out maybe ten thousand arithmetic operations in a 
> microsecond. Awesome.
> 
> MBD
> 
> 
> 
> ------------------------------
> 
> Message: 2
> Date: Fri, 05 Feb 2010 17:15:21 +0000
> From: Mark Davies <mark at snowtiger.net>
> To: ringing-theory at bellringers.net
> Subject: [r-t] Parallel searches [was Exhausted search spaces]
> Message-ID: <4B6C5229.5030500 at snowtiger.net>
> Content-Type: text/plain; charset=ISO-8859-1; format=flowed
> 
> Graham wrote,
> 
> > You create a processor pool. If there is a processor free, you assign it to
> > your current branch and backtrack your current process on to its next
> > branch. If a processor exhausts a branch or backtracks to its starting point
> > you return it to the pool.
> 
> Sounds about the size of it. It might be worth worrying a bit about the 
> size of the state frame you have to copy to a forked processor. If there 
> are frequent backtracks you might end up doing a lot of work copying and 
> restoring falseness tables etc. There are tricks that can avoid this, 
> but then again if the branches eventually become heavy enough, it's not 
> an issue anyway.
> 
> MBD
> 
> 
> 
> ------------------------------
> 
> Message: 3
> Date: Fri, 5 Feb 2010 21:41:30 -0000
> From: "Graham John" <graham at changeringing.co.uk>
> To: <ringing-theory at bellringers.net>
> Subject: Re: [r-t] Parallel searches [was Exhausted search spaces]
> Message-ID: <001601caa6ab$fae328d0$f0a97a70$@co.uk>
> Content-Type: text/plain; charset="us-ascii"
> 
> MBD wrote:
> 
> > It might be worth worrying a bit about the size of
> > the state frame you have to copy to a forked processor.
> 
> Yes, there is probably a significant overhead in checking whether there is a
> processor free too, but this is just optimisation of the algorithm.
> 
> > You can carry out maybe ten thousand arithmetic
> > operations in a microsecond. Awesome.
> 
> Indeed, as illustrated by a search for Cambridge Minor extents. SMC32
> completes the search before its clock has ticked over the first millisecond.
> 
> Graham
> 
> 
> 
> 
> ------------------------------
> 
> Message: 4
> Date: Fri, 05 Feb 2010 22:04:00 +0000
> From: Mark Davies <mark at snowtiger.net>
> To: ringing-theory at bellringers.net
> Subject: Re: [r-t] Parallel searches [was Exhausted search spaces]
> Message-ID: <4B6C95D0.3060803 at snowtiger.net>
> Content-Type: text/plain; charset=ISO-8859-1; format=flowed
> 
> Graham writes,
> 
> > Indeed, as illustrated by a search for Cambridge Minor extents. SMC32
> > completes the search before its clock has ticked over the first millisecond.
> 
> But that's a whole millisecond! A thousand times longer again than the 
> interval I was discussing. :-O
> 
> MBD
> 
> 
> 
> ------------------------------
> 
> Message: 5
> Date: Fri, 5 Feb 2010 23:21:25 +0000
> From: Simon Humphrey <sh at keystrata.co.uk>
> To: ringing-theory at bellringers.net
> Subject: Re: [r-t] Exhausted search spaces
> Message-ID: <20100205232125.000037aa at unknown>
> Content-Type: text/plain; charset=US-ASCII
> 
> On Fri, 05 Feb 2010 17:11:52 +0000
> Mark Davies <mark at snowtiger.net> wrote:
> 
> > I don't know why your PC is performing so badly on the SMC32
> > benchmark. Possibly your L2 or L3 caches aren't up to scratch, or
> > maybe disabling hyperthreading has made it worse. I'm not quite sure
> > why you've done that, as I don't think it'll give you any benefits! I
> > could be wrong, but I certainly wouldn't expect it to help SMC32.
> 
> The level 2/3 caches are quite likely to be a problem, I guess, it
> being an old processor.
> 
> If I leave hyperthreading enabled (which is the default), then according
> to the documentation the processor is effectively divided in two, and
> SMC is confined to using just 50% of the processing capacity. Resulting
> in run times twice as long, I would have thought. 
> 
> Now, hang on a minute, my run times ARE twice as long as yours. Hmm. I
> wonder if disabling hyperthreading has actually had any effect at all?
> Other than bamboozling Task Manager.
> 
> I'm convinced. I'll build a new machine.
> 
> SH
> 
> 
> 
> ------------------------------
> 
> Message: 6
> Date: Sat, 6 Feb 2010 00:22:27 -0000
> From: "Graham John" <graham at changeringing.co.uk>
> To: <ringing-theory at bellringers.net>
> Subject: Re: [r-t] Exhausted search spaces
> Message-ID: <000001caa6c2$7674c1f0$635e45d0$@co.uk>
> Content-Type: text/plain; charset="us-ascii"
> 
> Simon wrote:
> 
> > If I leave hyperthreading enabled, then according
> > to the documentation the processor is effectively
> > divided in two, and SMC is confined to using just
> > 50% of the processing capacity. Resulting in run
> > times twice as long, I would have thought. 
> 
> It is not splitting the processor, it is duplicating part of it. It parallel
> processes instructions to give a claimed 30% performance improvement. I ran
> a SMC32 comparison on a hyperthreading processor in 2004 (possibly similar
> to yours). The results for the "Full Monty" Cambridge S Major search were:-
> 
> 1h49m single instance (but still with hyperthreading turned on)
> 2h37m running two searches simultaneously
> 
> So running two searches simultaneously was 28% quicker than running two
> consecutively.
> 
> In summary, leave hyperthreading on - you can read your emails with one side
> of the processor while running SMC32 at full speed on the other.
> 
> Graham
> 
> 
> 
> 
> 
> 
> ------------------------------
> 
> Message: 7
> Date: Sat, 06 Feb 2010 11:05:12 +0000
> From: Mark Davies <mark at snowtiger.net>
> To: ringing-theory at bellringers.net
> Subject: [r-t] Hyperthreading [was Exhausted search spaces]
> Message-ID: <4B6D4CE8.9020006 at snowtiger.net>
> Content-Type: text/plain; charset=ISO-8859-1; format=flowed
> 
> Yes, hyperthreading definitely doesn't "split the processor in two", or 
> reduce resources allocated to a single thread.
> 
> All it really does is provide another set of registers, so that the 
> state for a second thread can be maintained without needing an expensive 
> context switch. Then, it is able to allocate existing processing 
> resources (instruction decoders, ALUs, branch prediction circuitry etc) 
> to the second thread when they are not being used by the main thread.
> 
> There are no additional execution units on the chip, so fundamentally 
> it's just another way of keeping all the ALUs running all the time. If 
> you had only one thread running on your machine (e.g. SMC32) you'd see 
> no difference with it on or off. However, there are always other things 
> going on, e.g. Windows services or other background processes, even if 
> you have no other programs open. Without hyperthreading, when another 
> process is scheduled for runtime, a context switch must occur, after 
> which the original thread (SMC32) is completely stopped for the next 
> time slice.
> 
> With hyperthreading enabled, other processes are more likely to be 
> scheduled to the second, "virtual" thread, and SMC32 will continue 
> (nearly) full bore whilst they are running.
> 
> So I think you've definitely got the wrong idea Simon: turning off HT 
> will make things worse, not better. To be fair though, if you're only 
> running SMC32, I doubt you'll see much improvement switching HT back on. 
> An old motherboard is more likely to be the problem, as you say.
> 
> MBD
> 
> 
> 
> ------------------------------
> 
> _______________________________________________
> ringing-theory mailing list
> ringing-theory at bellringers.net
> http://bellringers.net/mailman/listinfo/ringing-theory_bellringers.net
> 
> 
> End of ringing-theory Digest, Vol 65, Issue 8
> *********************************************

 		 	   		  
_________________________________________________________________
We want to hear all your funny, exciting and crazy Hotmail stories. Tell us now
http://clk.atdmt.com/UKM/go/195013117/direct/01/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://bellringers.net/pipermail/ringing-theory/attachments/20100206/f2920779/attachment-0004.html>