2
$\begingroup$

recently I've started thinking about caching problems in modern CPUs, where they struggle to adequately fetch program data (not instructions) in time, so that it can be computed further.
So then I came up with the idea, why don't we restrict random access on program data and make it all as a continuous stream (input and all eventual locals), which moves strictly in one direction through some "processing head", where you only have a possibility to read in some x amount of symols, write, let through and append symbols at the head position (this is a data stream, not an instruction stream).
The question is, whether you can effectively run computations in that system:
Is it possible to order all functions and allocate all local data/variables at compile time in such order that they will produce usable stream of data for all further functions, so that you will never need to "loop" the tape to access some particular element? (thus, emulating random access, by waiting for desired element to come by)
I've tried to look up this topic on the internet and found nothing. And maybe it is because this idea is obviously stupid, so no one bothers with it :)
Thank you for your help!

$\endgroup$
  • 1
    $\begingroup$ What have you tried? Have you tried going through an algorithms textbook to see which algorithms can be modified to be of this form? I think you'll quickly find that the answer is "no". $\endgroup$ – D.W. May 19 '14 at 7:48
  • 1
    $\begingroup$ What about binary search? $\endgroup$ – Raphael May 19 '14 at 7:54
  • $\begingroup$ @D.W. I've answered below. $\endgroup$ – artemonster May 19 '14 at 19:30
  • $\begingroup$ @Raphael binary search is a bitch. Most of recursive algorithms, which cannot be directly converted to a tail recursion are very problematic to realize with such "streaming". Many others are still ok, but it took a really long time to come up with datapath for these few algorithms that I've picked (Bubble Sort, FFT). $\endgroup$ – artemonster May 19 '14 at 19:33
  • 1
    $\begingroup$ Now that I think about it in terms of "streaming", the answers to this question of mine may be interesting for you. Also, I think sorting with its $\Omega(n \log n)$ comparisons lower bound may be a good candidate for a counter example; you'd have to show that you have to revisit earlier elements, though. Another buzzword worth googline is "online algorithms". In other words, models similar to what you have in mind have been studied, and they are restricted in power compared to TMs. $\endgroup$ – Raphael May 19 '14 at 21:11
0
$\begingroup$

No. Consider an algorithm on a graph (e.g., network flow). It fundamentally requires random access to memory. The restriction you propose would be painful and make many standard algorithms impossible.

$\endgroup$
  • $\begingroup$ Well, yes, I've tried. Basically, you try to make a tail recursive version of the algorithm, and there you go. $\endgroup$ – artemonster May 19 '14 at 19:29
  • 1
    $\begingroup$ @artemonster: How does tail recursion imply sequential memory accesses? You can do arbitrarily nasty stuff before the recursive call; consider e.g. Quicksort (there are tail-recursive versions, iirc). $\endgroup$ – Raphael May 19 '14 at 21:12
  • $\begingroup$ @Raphael it does not directly imply that. But it gives a way to transform the algorithm for stream processing: say, you have your tail-recursive function with stream of arguments. So after the pass you either send the stream back to the input, or you let it go (end-condition). So the computation in this case will loop the stream around this function, until end condition is achieved and you "let go" the stream. $\endgroup$ – artemonster May 20 '14 at 10:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.