Re: Binqry Tree sort

To Willem:


> Mergesort or quicksort won't work because they have a sequential stage
> that is O(n) and unparallelizable.


They are parallelizable. I read about their parallel implementation.


> Ah okay. Not sure if that makes much difference, just that you have to
> choose your interconnects very carefully.


The interconnection between processors are like the connection between
nodes of a
binary tree.


> The simplest for would probably be a bit like a neural net, with several
> rows, where each is interconnected with the next, two inputs and two outputs,
> where the node simply puts the smaller to one output and the larger to the
> other. Then is is a question of how to connect the nodes together.


Maybe you are right but I am not looking for an artificial life method
like ANNs.

In addition we have a network (Sorting network) as a parallel
architecture for just sorting elements of a set and its base structure
is ODD-EVEN Network. and the procesors do a little the same as what you

mentioned. The processor elements have 2 inputs and 2 outputs. The
first
output will be the smaller value and the second output will be the
greater
value.


But the processors which I want to use in my bianry tree architecture
all have just one output and they send the data to the parent(Upward)
and to
two children downward through connections.


To Logan:


> Basically, the root node is a huge bottleneck.


The root node has no bottle neck becasue it just receives data from its

2 children not more than that. And all data go from each tree level to
the next level, upward or downward, step by step & synchronously. Think

about the pipeline idea in Super-Scalar architectures .

To Chuck:



> You failed to quote context, making your post rather useless. That
> is why I asked you to read my sig and the URL it points to before
> posting again. Please do so.


OK Chuck. Is it true now?
To be honest I lost my self confidence. I'm a little afraid this time
you say: you have to answer individually. :)
Anyway, please let me know if I have other mistakes.

Thanks from all
Nejla

.

Relevant Pages

  • Re: Binqry Tree sort
    ... In addition we have a network as a parallel ... But the processors which I want to use in my bianry tree architecture ... The root node has no bottle neck becasue it just receives data from its ...
    (comp.programming)
  • Re: Structured Programming using Forth
    ... Since it takes multiple steps ... And that's because DSPs aren't just about MACs, ... The new SEAForth processor architecture is closer to a usable ... This network is coming from the ...
    (comp.lang.forth)
  • Re: [RFC][PATCH 2/4] RTC: SWARM I2C board initialization
    ... some places in the kernel tree, ... architecture-specific patches go through the relevant architecture tree. ... unlike the rest of the MIPS arch tree these days the Broadcom bits ... cause the i2c bus registration to fail, as the other platforms do not ...
    (Linux-Kernel)
  • Re: [PATCH 00/18] Make common x86 arch area for i386 and x86_64 - Take 2
    ... having a single bi-arch final tree is indeed intriquing and i didnt ... create bi-arch Makefiles and enable the building of each arch. ... of the same basic build architecture, ... If we did 3 separate hierarchies we'd have mixed state ...
    (Linux-Kernel)
  • Re: Should Xen be a sub-arch or a build option?
    ... would structure the tree were one to import it into CVS. ... if one were to import Xen support into CVS ... separate architecture. ... If it were me, I'd look at having it be a build option, much like PAE ...
    (freebsd-arch)