Radio Computing • Internet and Co • Programming with Stair • Sorting and Searching (Previous | Next)

How can a memory cell communicate with as many other ones by radio chips at different frequencies in order to support parallel computing? How can in this way sorting of n values be improved from \(\mathcal{O}\)(n log n) to \(\mathcal{O}\)(1) and thus the indexing of tables in databases become obsolete?

If each radio chip transmits (simultaneously) at the frequency that corresponds to the value, transformed into the smallest positive natural interval valid for all values, of the associated memory cell, then the counterpart stations receive these new values sorted in \(\mathcal{O}\)(1) and they can output them in \(\mathcal{O}\)(1), if they are hierarchically organised as a binary tree, while first the 0-node and then the 1-node sends to its parent node.

If the parent node is still not taken, it stores the value of the 0-node. For each free further parent node, the procedure is the same and the 1-node is pulled behind. This is altogether possible in \(\mathcal{O}\)(log n), thus enabling an output of all nodes by traversing the resulting binary tree in \(\mathcal{O}\)(n). Equal values are first made different by appending a sequence number in \(\mathcal{O}\)(n).

It is clear that the radio distances depend only on the size of the radio chips and that the radio must not be disturbed from the outside. Here weak (if need be shielded) signals and a predetermined frequency range are advisable. Possibly, first an implementation in datacentres is provided, as long as the radio chips are still relatively large, but this is for example not a big problem because of the increasing cloud computing.

For fewer frequencies than values to be transmitted, use FSO or microwaves, or double the number of transmission runs for each additional bit. If the frequency values are smaller than the values to be transmitted, so another transmission run for the subsequent sorting is necessary, for every transcending by a further frequency range. If applicable, for additionally occurring values, overflow areas are advisable (e.g. for table queries).

If one arranges the radio chips in a straight line, and puts in each case two of these lines crosswise one above the other, they can, if they are confronted with, send without intersection, and one gets along with one or few frequencies. Thus, k + 1 tables can be joined in a query in \(\mathcal{O}\)(1) instead of \(\mathcal{O}\)(n log^{k} n). However, the necessity for serial processing sets limits to the parallel (radio) computing.

The radio technology can also be used to implement parallel transmission of parallel adders or other (linear) arithmetic operations (e.g. comparisons). In conjunction with networks and fast data transmission (e.g. DSL), it can be parallel calculated in combination (e.g. to solve (linear) optimisation problems in linear time). Also associative problems can be parallel solved (better than in the brain).

© 2011 by Boris Haase

• disclaimer • mail@boris-haase.de • pdf-version • bibliography • subjects • definitions • statistics • php-code • rss-feed • top