On Wed, 10 May 2006 17:53:36 +0900, Masataka Ohta wrote:
Sometimes, pipelining can improve performance by a small constant factor with a small amount of additional hardware.
Sorry: *LOL* With this statement ("small constant factor") you have just proven that you are far away with your routing table lookup theory from any real design. With today's CPU's we are talking of about 20 pipeline stages ... The advances in processing speed in the last ten years are - to a significant degree - based on advanced in multi- level and parallel pipelined CPU architectures (called superscalar processors).
Pipelining requires pipeline resigters.
If you have too much stages of pipelining, additional amount of pipeline registers kills the benefit.
Sorry, but it seems to me that you are talking about developments you have never been involved in. Pipeline registers are D-Flipflops, build as Master Slave static or e.g. using transfer gates, they are the _basic_ elements of any real IC design. These elements determinate - together with the conditional logic between them - the maximum permitted clock frequency. RAM is never ever faster than a single D-Flipflop using the same technology. Pipeline _stalls_ are a problem with CPU's, if we talk about an conditional instruction and if the branch prediction fails. With IP routing with multistage lookup there simply aren't such conditional instructions. IP routing fits ideal with pipelining, as there is no dependence between different IP packets, the first section of the pipeline decodes the first portion of the IP address, then passes the packet header to the next section responsible for the next portion of the address, at this time the first section starts decoding the next packet etc. If a delay is required, e.g. opening a new RAM page based on the first decode, then the packet header is put in the loop for one cycle. This is the difference between _throughput_ and _latency_ required by a forwarding engine. Thus if constructed the right way, handling reasonably large tables should not be a problem at all. Best Regards Oliver Bartels Oliver Bartels F+E + Bartels System GmbH + 85435 Erding, Germany oliver@bartels.de + http://www.bartels.de + Tel. +49-8122-9729-0