4
$\begingroup$

In my previous question ( Can Turing machines be converted into equivalent Lambda Calculus expressions with a systematic approach? ), I got the answer that it is indeed possible.

And as I have read before, every program written in all programming languages is convertible to a Turing Machine. And of course, since there are no side effects and no order in calculating a lambda expression, parallelization is infinitely possible, and it can break down to computing one lambda function on a separate machine.

So with having these three facts in mind, An interesting question comes to mind. Since every program written in every programming language has an equivalent Turing machine, Turing machines are convertible to Lambda Calculus expression through an algorithm, and Lambda expressions are infinitely parallelizable, can every program be parallelized automatically and infinitely?

EDIT : I think I have to clear out one thing. By infinitely parallelizing, I mean to parallelize till the point where it benefits us, so the arguments about the size of parallelizations are not valid. For example, by having five cores of cpu, one can utilize all of his\her cores by these approach.

Improve this question
$\endgroup$
13
  • 1
    $\begingroup$ see eg computing granularity. it both correct/ incorrect that computation is "infinitely parallelizable". am not sure if that concept is studied theoretically, might look into it. $\endgroup$ – vzn Oct 23 '15 at 15:48
  • 2
    $\begingroup$ Can you define what you mean by "infinitely parallelizable"? I think you have an erroneous premise/assumption in your question. It is not true that "parallelization is infinitely possible" for lambda expressions. I suspect you should start by asking about parallelization of lambda expressions, before you try to apply that understanding to other things like Turing machines. $\endgroup$ – D.W.♦ Oct 23 '15 at 16:23
  • 3
    $\begingroup$ That makes no sense to me. "till the point it stops being useful" -- so what could possibly violate that condition? By that definition everything is 'infinitely parallelizable'. For example, if it's not parallelizable at all, then you're already at the point where parallelization stops being useful, so your definition implies that a program that can't be parallelized is something you'd consider 'infinitely parallelizable'. I don't see the sense in that. I suspect you might want to expand your question, to clarify the motivation and context and what you mean by these terms. $\endgroup$ – D.W.♦ Oct 23 '15 at 16:34
  • 1
    $\begingroup$ @D.W. ok first of all, you asked me what I meant by infinitely parallelizable, then you didn't wait for my answer, and wrote your answer. I think that if you waited a bit, I could have clarified my means, like I'm doing now. So there is no need to attack me in every way possible. By infinitely parallelizable, I meant the way most automatic parallelizations work, by identifying blocks of code that do not have effects on each other and run them parallel to each other. And I think because of the properties of lambda calculus, this can happen a lot! So I meant it that way. $\endgroup$ – Ashkan Kazemi Oct 23 '15 at 16:43
  • 1
    $\begingroup$ I'm sorry to hear that you seem to have interpreted my comments/answer as a personal attack. I can assure you that they were not intended that way. They are my best attempt to try to answer your question (and to articulate how you can make the question clearer), as well as I was able, given the information in front of me. As far as why I answered immediately based on my reading of your question, some posters prefer to receive a best-attempt answer rapidly rather than wait for a possibly-better answer later -- it's fine if you're not in that camp (and I admire that). $\endgroup$ – D.W.♦ Oct 24 '15 at 0:02
5
$\begingroup$

If you're working in the strict lambda calculus, everything can be automatically parallelized. In particular, when evaluating a function application, the function and the argument can always be evaluated in parallel.

However, it cannot be infinitely parallelized. There are inherent data dependencies: the result of a function application can't be determined until both the argument and the function have been evaluated, meaning that you need to wait for your threads to both finish, then synchronize.

This is still relevant with your clarified definition of infinitely. For example, if you have 5 processors, it's possible that a particular program can only ever use 4 processors, because of the data dependencies.

Moreover, while this is automatic, it is not "performance for free." In practice, there is non-trivial overhead to creating and synchronizing threads. Moreover, it's difficult to do this in a way that scales only to the current number of processors: if you have 5 cores, the automatic parallelization might generate 6 threads, and in general, it's not possible to know at compile-time how many threads will be active at a given time.

So, you can automatically make a program that runs massively parallel, but with the current state of affairs, it will likely be slower than your original.

It's also worth mentioning that, in practice, this becomes difficult with shared access to resources and IO. For example, a real world program might write to a disk, which can cause problems if done in parallel without control. This is something that can't be modeled by the standard lambda calculus.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I didn't get the part about the data dependency, since there aren't any in strict lambda calculus. and You know, maybe in theory there are examples that running the program with this sort of parallelization might be slower, but I think in most cases you get a lot of performance boost and resource utilization. As for I/O, well, we can't do anything about that, can we? $\endgroup$ – Ashkan Kazemi Oct 23 '15 at 19:12
  • 1
    $\begingroup$ In lambda calculus, you don't have to worry about race conditions, but when you perform an operation on two values, you still need to know what both those values are, and if you have threads computing them, you have to wait until they're done to perform the operation. Likewise, you don't get a performance boost if the algorithm doesn't know when to stop. If you have 6 cores, but 100000 threads, your scheduler and switching overhead will greatly outweigh the benefits of parallelism. You can make it maximally parallel, but not always optimally parallel. $\endgroup$ – jmite Oct 23 '15 at 19:15
  • $\begingroup$ You talk about working strictly in lambda calculus. Since Turing machines and lambda calculus are equivalent, does this imply that any problem that can be solved with a Turing machine can be parallelized? $\endgroup$ – moonman239 Jun 25 '20 at 22:20
  • $\begingroup$ @MontanaBurr Yes, it does. But computer programs seldom correspond nicely to Turing Machine problems, because we are interested in what they do (print, write to disk, etc.) and not just what they compute. And like I say in the answer, this automatic parallelization isn't always efficient. $\endgroup$ – jmite Jun 25 '20 at 23:02
3
$\begingroup$

No, lambda expressions are not "infinitely parallelizable" (whatever that means).

For instance, consider the lambda expression $\lambda x . x$. This is the identity function. It takes $1$ step of computation to compute it. It cannot be parallelized; you can't somehow speed up the computation by using a parallel computer, and you certainly can't speed it up "infinitely".

So no, it's not true that every lambda expression can be "infinitely parallelized", and it's not true that every program can be "infinitely parallelized".

Improve this answer
$\endgroup$
3
  • $\begingroup$ you had to wait and see what I meant by infinitely parrallilazble. By that I meant that you can maximize parallelization as much as possible, but not doing it when it doesn't prosper us. your example is exactly the place where it stops being useful and I didn't mean those times. $\endgroup$ – Ashkan Kazemi Oct 23 '15 at 16:28
  • $\begingroup$ @AshkanKzme, My answer is based on my best attempt to understand what you were asking, given the state of the question at the time that I answered; I don't see anything unreasonable about that. This is why it is important to make sure that the initial version of your question is clear about what you are asking. Otherwise you risk wasting the time of answerers and/or getting answers that weren't quite what you were looking for. $\endgroup$ – D.W.♦ Oct 23 '15 at 16:38
  • $\begingroup$ yes, but everything changes when you are not clear about the intent of my question, so you ask a question about it, then do not wait for a clarification and write your answer anyway. $\endgroup$ – Ashkan Kazemi Oct 23 '15 at 16:44
1
$\begingroup$

"Infinite parallelization" is not studied too much in CS because processors like other computational resources eg "time/ space" are almost always regarded as finite but here are at least two contexts where it shows up.

In the case of parallelization, Amdahl's law states that if P is the proportion of a program that can be made parallel (i.e., benefit from parallelization), and $1 − P$ is the proportion that cannot be parallelized (remains serial), then the maximum speedup that can be achieved by using $N$ processors is $S(N) = ...$ . In the limit, as $N$ tends to infinity, the maximum speedup tends to $\frac{1}{1 − P}$.

So it is more of a theoretical concept or abstraction possibly sometimes used in mathematical theorems that does not really have direct applications and may break down somewhat where continuous math is used to represent discrete math problems.

In parallel computing there is an informal concept of "granularity". fine grained problems are somewhat analogous to many sand grains and can be split among many processors. roughly, these are also known as embarassingly parallel problems. But as an analogy, one cannot split a grain of sand in computation. There are still atomic-level operations that cannot be split further. Less fine grained problems have bigger "grains" that cannot be split as easily.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I think the use of amdahl's law here was irrelevant. Plus please don't get too worked up around the word infinitely. $\endgroup$ – Ashkan Kazemi Oct 23 '15 at 16:30
  • 1
    $\begingroup$ Amdahl's law is definitely relevant here. Strict lambda calculus says that parallelization is safe, but there is still only a part of the program that can be run in parallel. $\endgroup$ – jmite Oct 23 '15 at 19:20

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.