Lambda the Ultimate

Where does the 759 cycles in the example come from? If this is a vector of independent adders then shouldn't it take 32 cycles or less? It would be helpful if you could explain what these cycles are and how they related to the intermediate steps in the computation.

I've had a look through your report and I think that I can see what you are doing. But unless I've missed something (which is quite likely given the size of your report) I can't see why you are doing it. To clarify - I can understand the justification for distributing the computation throughout the memory so that each memory location becomes a simplified processor. But the way that you have defined it I cannot see any form of locality, which is essential to making claims about scalability and verifiability.

Your A-RAM contains four instructions: the two forms of write, the conditioned skip and the jump are clearly universal (as I can unfold any mapping over a finite number of bits into a decision tree for each output bit and thus build comparators for the jumps). But each read and write can access any location - there is no concept of locality within the list of registers that constrains which locations an instruction in a register can access. So the interconnect must be fully connected between registers, must synchronise on each cycle and must terminate with an error on write collisions. This doesn't seem to be an improvement on a standard shared-memory multi-threaded machine.

Have you seen this recent work that aims at a similar area, but restricts the communication topology between the cells?

The current focus on asynchronous designs arises out of several factors, not least of which is that asynchronism is part of the zeitgeist. There is a quasi-political consideration, that because individuals, corporations and sovereign nation states have a reasonable desire to keep their internal workings private, and not subject to centralised (read synchronised) control, this aspiration should be reflected in the design of networks of computational devices. Freedom is an absolutely legitimate concern, but it is not obvious why it has any relevance to the purely technical issues relating to the foundations and the implementation of high performance computing. Agent based concurrency has dominated theoretical studies for decades, without resolving the parallel computing crisis -- there is a need to consider other approaches.

Large computer architectures can be clocked, if there is sufficient investment in synchronisation mechanisms. The establishment of a global clock, does not require signals to travel across the entire radius of an environment, or through wires. Optoelectronic technology [1] enables very short cycle times. In [2] Miller states, “It is likely possible to retain absolute timing accuracy in the delivery of optical clock signals of ~10-100 picoseconds over a computer room (tens of meters) without any special technology.” If thats true, it should for example be feasible to synchronise millions of 3Ghz processors. I dont think architectures for synchronic computation would need to synchronise over any thing like that kind of area to be competitive.

In a physical implementation, communication times between storage elements described in Space modules may vary, but all communications would succeed (barring hardware failure) because the programming model is set up to be Exclusive Write. Verification from that point of view would not be necessary. I would be grateful for any links describing Tileras and Clearspeed’s issues, for future comparison.

In a wave based fully connected scheme for n elements, there is a potential for O(n) area complexity. Wave based information may be transmitted by electromagnetic, spintronic, or possibly some other form of radiation. Digital information is encoded through the modulation of a wave’s amplitude or phase, transmitted through the wave medium by an emitter, and received by a detector and decoded. A multitude of links can be realised in a wave medium or free space, potentially without crosstalk or interference, in at least two ways.

Processing elements are laid out in a plane, and an element incorporates at least one pair of a fixed detector and a pointable emitter or reflector, to aim at most one other element by bouncing a transmission through free space off of a reflecting mirror, or deflecting layer. Propagation times may vary depending on the total flight distance between points. A single emitter is point to point, and does not support broadcast mode.

Exclusively employing the technique of wavelength division multiplexing, each processing element is designated it’s own specific wavelength interval, and is equipped with a single wave emitter/detector mechanism, where the wavelength configuration of at least the detector must be adjustable/tunable. The plane of processing elements is sandwiched with a wave medium. Propagation times for messages again may vary, depending on distances between points. Each element may omnidirectionally broadcast on it’s own emitting wavelength, through the medium to a plurality of receiving elements, providing the receiving element’s detector is tuned to the emitter’s wavelength.

In both cases, there is no requirement for multiplexers/demultiplexors with non linear space and time complexity, merely for an element to have a tunable or pointable receiver/emitter.

[1] Aparna Bhatnagar et al., “Receiverless detection schemes for optical clock distribution,” in Quantum Sensing and Nanophotonic Devices, vol. 5359 (presented at the Quantum Sensing and Nanophotonic Devices, San Jose, CA, USA: SPIE, 2004), 352-359.
[2] D.A.B. Miller, “Rationale and challenges for optical interconnects to electronic chips,” Proceedings of the IEEE 88, no. 6 (2000): Section C.1., pg 734.

In addition, I was trying to generate interest into the question of whether it matters that the λ-calculus and the Turing Machine are not suited to executing high level processes. I argue in chapter 9 of arxiv link that neither can feasibly support random access memory or parallel composition of modules, which are needed for the practical simulation of high level computation, in terms of primitive steps. In the case of the λ-calculus, the problem partly derives from adopting a non-spatial, context free grammar with high structural variability, where any branch of the syntax tree may be indefinitely long, as the syntax for the formalism. Unfortunately graph rewriting is not a feasible solution because pattern matching is NP-complete.

The Curry-Howard isomorphism is a means of relating proofs in various, conventional tree based logics, to terms in various extensions of conventional tree based λ-calculus. Can one assume that the difficulty of expressing high level programs and consequently high level proofs in the λ-calculus, does not place a limit on the practical utility of the Curry-Howard isomorphism?

I would like to argue that type theory’s overall agenda is constrained by focusing on standard tree based logics and calculi. A future paper will describe how simulation efficient compute models in the α-Ram family can provide a platform for spatialising logic and mathematics, and thereby provide an alternative means of realising mathematical argument as a form of computation. Complex structures, procedures, and proofs, could be brought into computational life as abstract data structures, virtual algorithms, and interstring-based logic programs defined in terms of a primitive formal model. The intention is to allow the use of only enough standard set theory and informal logic, for the definition of a low level, generic, synchronic model of computation. The Synchronic B-Ram defined in 3.2.2 of the linked report fulfills this requirement. It is proposed that the following steps are then taken:

(i) The construction of a native, high level interlanguage programming environment, able to support virtual programs and abstract data types.
(ii) The definition of a prenexed and interstring-based form of predicate logic called interlogic, together with a deterministic parallel deduction algorithm that is executable on the model.
(iii) Finally, the recasting of the rest of mathematical discourse concerning structures derived from computable algebras, as interstring-based reasoning about virtual programs and abstract data types.