From mboxrd@z Thu Jan 1 00:00:00 1970 Date: Tue, 20 Oct 2009 02:57:38 +1100 From: Sam Watkins To: Fans of the OS Plan 9 from Bell Labs <9fans@9fans.net> Message-ID: <20091019155738.GB13857@nipl.net> References: <<20091015105328.GA18947@nipl.net>> <4030fb6ae37f8ca8ae9c43ceefbdf57b@ladd.quanstro.net> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.13 (2006-08-11) Subject: Re: [9fans] Barrelfish Topicbox-Message-UUID: 8b539972-ead5-11e9-9d60-3106f5b1d025 On Sat, Oct 17, 2009 at 07:45:40PM +0100, Eris Discordia wrote: > Another embarrassingly parallel problem, as Sam Watkins pointed out, arises > in digital audio processing. The pipelining + divide-and-conquer method which I would use for parallel systems is much like a series of production lines in a large factory. I calculated roughly that encoding a 2-hour video could be parallelized by a factor of perhaps 20 trillion, using pipelining and divide-and-conquer, with a longest path length of 10000 operations in series. Such a system running at 1Ghz could encode a single 2-hour video in 1/100000 second (latency), or 2 billion hours of video per second (throughput). Details of the calculation: 7200 seconds * 30fps * 12*16 (50*50 pixel chunks) * 500000 elementary arithmetic/logical operations in a pipeline (unrolled). 7200*30*12*16*500000 = 20 trillion (20,000,000,000,000) processing units. This is only a very rough estimate and does not consider all the issues. The "slow" latency of 1/100000 second to encode a video is due to Ahmdal's Law, assuming a longest path of 10000 operations. The throughput of 2 billion hours of video per second would be achieved by pipelining. The throughput is not limited by Ahmdal's Law, as a longer pipeline/network holds more data. Ahmdal's Law gives us a lower limit for the time taken to perform a task with some serial components; but does not limit the throughput of a pipelining system, the throughput is simply one data unit per clock cycle. In reality, it would be hard to build such a system, and one would prefer a system with much less parallelization. However, the human brain does contain 100 billion neurons, and electronic units can be smaller than neurons. My point is, one can design systems to solve practical problems that use almost arbitrarily large numbers of processing units running in parallel. Sam