New book on Carl Adam Petri and my chapter “Living Lattices” in it

A very nice new book “Carl Adam Petri: Ideas, Personality, Impact“, edited by Wolfgang Reisig and Grzegorz Rozenberg, has just been published by Springer:

https://link.springer.com/book/10.1007/978-3-319-96154-5

Newcastle professors, Brian Randell, Maciej Koutny and myself contributed articles for it.

An important aspect of those and other authors’ articles is that they mostly talk about WHY certain models and methods related to Petri nets have been investigated rather than describing the formalisms themselves. Basically, some 30-40 years of history are laid out on 4-5 pages of text and pictures.

My paper  “Living Lattices” provides a personal view of how Petri’s research inspired my own research, including comments on related topics such as lattices, Muller diagrams, complexity, concurrency, and persistence.

The chapter can be downloaded from here:

https://link.springer.com/chapter/10.1007/978-3-319-96154-5_28

There is also an interesting chapter by Jordi Cortadella “From Nets to Circuits and from Circuits to Nets”, which reviews the impact of Petri nets in one of the domains in which they have played a predominant role: asynchronous circuits. Jordi also discusses challenges and topics of interest for the future. This chapter can be downloaded from here:

https://link.springer.com/chapter/10.1007/978-3-319-96154-5_27

 

Switched electrical circuits as computing systems

We can define computations as processes of working of electrical circuits which are associated with sequences of (meaningful) events. Let’s take these events as discrete, i.e. something that can be enumerated with integer indices.

We can then map sequences of events onto integer numbers, or indices. Events can be associated with the facts of the system reaching certain states. Or, in a more distributed view, individual variables of the system, reaching certain states or levels. Another view is that a component in the system’s model moving from one state to another.

To mark such events and enable them we need sensory or actuating properties in the system. Why not simply consider an element called “switch”:

Switch = {ON if CTRL= ACTIVE, OFF if CTRL = PASSIVE}

What we want to achieve is to be able to express the evolution of physical variables as functions of event indices.

Examples of such computing processes are:

  • Discharging capacitance
  • Charging a (capacitive) transmission line
  • Switched cap converter
  • VCO based on inverter ring, modelled by switched parasitic caps.

The goal of modelling is to find a way of solving the behaviour of computational electrical circuits using “switching calculus” (similar to Heaviside’s “operational calculus” used to solev differential equations in an efficient way).

Some of Leonid Rosenblum’s works

L. Ya. Rosenblum and A.V. Yakovlev.
Signal graphs: from self-timed to timed ones,
Proc. of the Int. Workshop on Timed Petri Nets,
Torino, Italy, July 1985, IEEE Computer Society Press, NY, 1985, pp. 199-207.

https://www.staff.ncl.ac.uk/alex.yakovlev/home.formal/LR-AY-TPN85.pdf

A paper establishing interesting relationship between the interleaving and true causality semantics
using algebraic lattices. It also identifies an connection between the classes of lattices and the property
of generalisability of concurrency relations (from arity N to arity N+1),
i.e. the conditions for answering the question such as,
if three actions A, B and C are all pairwise concurrent, i.e. ||(A,B), ||(A,C), and ||(B,C), are they concurrent “in three”, i.e. ||(A,B,C)?
L. Rosenblum, A. Yakovlev, and V. Yakovlev.
A look at concurrency semantics through “lattice glasses”.
In Bulletin of the EATCS (European Association for Theoretical Computer Science), volume 37, pages 175-180, 1989.

https://www.staff.ncl.ac.uk/alex.yakovlev/home.formal/lattices-Bul-EATCS-37-Feb-1989.pdf

Paper about the so called symbolic STGs, in which signals can have multiple values (which is often convenient for specifications of control at a more abstract level than dealing with binary signals) and hence in order to implement them in logic gates one needs to solve the problem of binary expansion or encoding, as well as resolve all the state coding issues on the way of synthesis of circuit implementation.

https://www.staff.ncl.ac.uk/alex.yakovlev/home.formal/async-des-methods-Manchester-1993-SymbSTG-yakovlev.pdf

Paper about analysing concurrency semantics using relation-based approach. Similar techniques are now being developed in the domain of business process modelling and work-flow analysis: L.Ya. Rosenblum and A.V. Yakovlev. Analysing semantics of concurrent hardware specifications. Proc. Int. Conf. on Parallel Processing (ICPP89), Pennstate University Press, University Park, PA, July 1989, pp. 211-218, Vol.3

https://www.staff.ncl.ac.uk/alex.yakovlev/home.formal/LR-AY-ICPP89.pdf

Моделирование параллельных процессов. Сети Петри [Текст] : курс для системных архитекторов, программистов, системных аналитиков, проектировщиков сложных систем управления / Мараховский В. Б., Розенблюм Л. Я., Яковлев А. В. – Санкт-Петербург : Профессиональная литература, 2014. – 398 с. : ил., табл.; 24 см. – (Серия “Избранное Computer Science”).; ISBN 978-5-9905552-0-4
(Серия “Избранное Computer Science”)

https://www.researchgate.net/…/Simulation-of-Concurrent-Processes-Petri-Nets.pdf

Leonid Rosenblum passes away …

Today In Miami at the age of 83 passed away a well known Russian and American automata theory scientist Leonid Rosenblum. He was my mentor and closest friend. Here is some brief information about his career. In Russian.

Леонид Яковлевич Розенблюм (5 марта 1936 г. – 2 апреля 2019 г.), канд. техн.наук, доцент – пионер мажоритарной логики, самосинхронной схемотехники, теории и применений сетей Петри в моделировании и проектировании цифровых схем и параллельных систем.В течение 20 лет, с 1960г. по 1980г., занимался с коллегами (в группе профессора В.И. Варшавского) наукой и приложениями (например, разработкой новой схемотехники и надежных бортовых компьютеров) в Вычислительном центре Ленинградского отделения Математического института им. В.А. Стеклова АН СССР.

С 1981г. по 1989 г. работал доцентом кафедры математического обеспечения и применения ЭВМ в ЛЭТИ им. В.И. Ульянова-Ленина (ныне Санкт-Петербургский государственный электротехнический университет). В 90-х годах после эмиграции в США работал адъюнкт-профессором в Бостонском университете, а также исследователем в Гарвардском университете.

Соавтор/автор пяти книг, около двух сотен различных изданий, учебных пособий, статей и обзоров, более 40 авторских свидетельств на изобретения.

Среди его учеников – профессора университетов России, Великобритании, США, Финляндии и других стран, сотрудники институтов АН Российской Федерации, таких как Институт Проблем Управления, а также известных отечественных и зарубежных компаний, таких как Intel, Cadence, Xilinx и т.д.

Леонида Яковлевича отличало врожденное свойство видеть в людях только положительные качества, помогать всем и во всем, и конечно необыкновенное чувство юмора. Эта утрата для огромного числа людей повсюду, всех кому посчастливилось его знать или слышать о нем.

Вечная память, дорогой Лека!

Leonid Yakovlevich Rosenblum (March 5, 1936 – April 2, 2019), Cand. Technical Sciences, Associate Professor – a pioneer of majority logic, self-timed circuit design, theory and applications of Petri nets in the modeling and design of digital circuits and parallel systems.

For 20 years, from 1960 to 1980, he worked with his colleagues (in the group of Professor VI Varshavsky) with science and applications (for example, developing new circuitry and reliable on-board computers) at the Computing Center of the Leningrad Branch of the Mathematical Institute. V.A. Steklov Academy of Sciences of the USSR.
From 1981 to 1989, he worked as an associate professor at the Department of Software and Computer Applications at LETI named after Ulyanov-Lenin  (now St. Petersburg State Electrotechnical University). In the 90s, after emigration to the United States, he worked as an adjunct professor at Boston University, as well as a researcher at Harvard University.
Co-author / author of five books, about two hundred different publications, textbooks, articles and reviews, more than 40 certificates of authorship for inventions.

Among his students are professors from universities in Russia, the United Kingdom, the United States, Finland and other countries, employees of institutes of the Academy of Sciences of the Russian Federation, such as the Institute of Management Problems, as well as well-known domestic and foreign companies such as Intel, Cadence, Xilinx, etc.

Leonid Yakovlevich was distinguished by the innate ability to see in people only positive qualities, to help everyone and in everything, and of course an extraordinary sense of humor. This is a great loss for a huge number of people everywhere, all who were lucky enough to know or hear about him.
Rest in peace, dear Leo!

 

My Talk at the RAEng Fellows Day at Newcastle

I was invited to give a talk on my Research at the Royal Academy of Engineering event, held in Newcastle on the 28th January 2019.

The title of the talk is “Asynchronous Design Research or Building Little Clockless Universes

The PDF of the slides of my talk are here: http://async.org.uk/presentations/AlexYakovlev-Research-RAEngEvent-280119.pdf

I only had 15 minutes give to me. Not a lot to talk about the 40 years of research life. So, at some point in preparing for this talk, I decided that I’ll try to explain what the research in microelectronic systems design is about, and in particular how my research in asynchronous design helps it.

Basically, I tried to emphasize on the role of ‘time control’ in designing ‘little universes’, where the time span covered by our knowledge of what’s is going on in those systems and why is between 1 few picoseconds (transistor switching event) and hours if not days (applications life times). So we cover around 10^18 events. How does it compare to the life of universe – being “only” around 10^13 years. Are we as powerful as gods in creating our ‘little universes’.

So, in my research I want to better control TIME at the smallest possible scale, surprisingly but, by going CLOCK-LESS! Clocking creates an illusory notion of determinacy in tracking events and their causal-relationship. Actually, it obscures such information. Instead by doing your circuit design in a disciplined way, such as speed-independent circuit design, you can control timing of events down to the best levels of granularity. In my research I achieved that level of granularity for TIME. It took me some 40 years!

But, furthermore, more recently, say in the last 10 years, I have managed to learn pretty well how to manage power and energy also to that smallest possible level, and actually make sure that energy consumption is known to the level of events controlled in a causal way. Energy/power-modulated computing, and its particular form of power-proportional computing, is the way for that. We can really keep track of where energy goes down to the level of a few femto-Joules. Indeed if a parasitic capacitance of an inverter output in modern CMOS technology is around 10fF and we switch it at Vdd=1V, we are talking about minimum energy quantity of CV^2=10fJ= 10^-14J per charging/discharging cycle (0-1-0 in terms of logic levels). Mobile phones run applications that can consume energy at the level of 10^4J. Again, like with time we seem to be pretty well informed about what’s going on in terms of energy covering 10^18 events! Probably, I’ll just need another 5 or so years to conquer determinacy in energy and power terms – our work on Real-Power Computing is in this direction.

Now, what’s next, you might ask? what other granularification, distribution and decentralization can we conquer in terms of building little universes!? The immediate guess that comes to my mind is the distribution (in time and energy directions) of functionality, and to be more precise intelligence. Can we create the granules of intelligence at the smallest possible scale, and cover same orders of magnitude. It is a hard task. Certainly, for CMOS technology it would be really difficult to imagine that we can force something like a small collection of transistors dynamically learn and optimize its functionality. But there are ways of going pretty close to that. One of them seems to be the direction of learning automata. Read about Tsetlin automata, for example (https://en.wikipedia.org/wiki/Tsetlin_machine) , in the recent work of Ole-Christoffer Granmo.

 

 

 

 

On the Role of Mathematics for humanity in building physical reality

Mathematics is a (or, probably, the only!) language that enables ideas about physics be communicated between people across different generations and across different cultures.

Inevitably, it ”suffers” from approximation and abstraction compared to physical reality. A bit like an impressionist painting reflects the real picture.

The question is what and how much is sacrificed here.

One test of whether the sacrifice is acceptable or not is in the way how people, while using mathematics, can build physical objects such as airplanes, cars, bridges, radios, computers etc. If they can and at a reasonable cost, then the language is adequate to the purpose.

For example, it seems that the mathematical language of Heaviside’s operational calculus is sufficient for the purposes of designing and analysing electrical circuits of good quality and in an acceptable time.

Another example, the language of Boolean algebra is sufficient to design logic circuits if we clock them safely so that they don’t produce any hazards. If, however we don’t clock them safely, we need other ways to describe causal relationships between events, such as Signal Transition Graphs.

 

 

My PhD Thesis (1982) – scanned copy in pdf

I have finally managed to scan my PhD thesis “Design and Implementation of Asynchronous Communication Protocols in Systems Interfaces” in Russian (“Проектирование и реализация протоколов асинхронного обмена информацией в межмодульном интерфейсе”)

The thesis is spread between several files (total – 255 pages):

Title, Contents and Introduction:

Chapter 1 (General characterization of the methods of formal synthesis and analysis of communication protocols): 

Chapter 2 (Formalization of the behaviour of interacting objects and communication protocols):

Chapter 3 (Interpretation of asynchronous processes and use of interpreted models for the description and analysis of protocols):

Chapter 4 (Organization of aperiodic interface of intermodular communication):

Conclusion and References:

Appendinces (1-5):

(1) Example of context procedure

(2) Example of controlled protocol

(3) Application of Petri nets to specification of asynchronous discrete structures

(4) Information transfer on three-state lines

(5) Analysis and implementation of the TRIMOSBUS interface

Exploitation confirmation letter from Ufa plant

 

Bridging Async and Analog at ASYNC 2018 and FAC 2018 in Vienna

I attended ASYNC 2018 and FAC 2018 in Vienna in May. It was the first time these two event were collocated back to back, with FAC (Frontiers of Analog CAD) to follow ASYNC.

See http://www.async2018.wien/

I gave an invited ‘bridging’ keynote “Async-Analog: Happy Cross-talking?”.

Here are the slides in pdf:

https://www.staff.ncl.ac.uk/alex.yakovlev/home.formal/talks/ASYNC18-FAC18-keynote-AY-last.pdf

 

 

 

Energy-vector, momentum, causality, Energy-scalar …

Some more interesting discussions with Ed Dellian has resulted in this ‘summary’, made in context with my current level of understanding of Catt Theory of electromagnetism):

  1. Energy current (E-vector) causes momentum p.
  2. Causality is made via the proportionality coefficient c (speed of energy current)
  3. Momentum p is what mediates between E-vector and changes in the matter.
  4. Momentum p is preserved as energy current hits the matter.
  5. Momentum in the matter presents another form of energy (E-scalar).
  6. E-scalar characterises the elements of the matter as they move with a (material) velocity.
  7. As elements of the matter move they cause changes in Energy current (E-vector) and this forms a fundamental feedback mechanism (which is recursive/fractal …).

Telling this in terms of EM theory and electricity:

  • E-vector (Poynting vector aka Heaviside signal) causes E-scalar (electric current in the matter).
  • This causality between E-vector and E-scalar is mediated by momentum p causing the motion of charges.
  • The motion of charges with material velocity causes changes in E-vector, i.e. the feedback effect mentioned above (e.g. self-induction)

I’d be most grateful if someone refutes these items and bullets.

I also recommend to read my blog (from 2014) on discretisation

On Quantisation and Discretisation of Electromagnetic Effects in Nature

Real Nature’s proportionality is geometric: Newton’s causality

I recently enjoyed e-mail exchanges with Ed Dellian.

Ed is one of the very few modern philosophers and science historians who read Newton’s Principia in original (and produced his own translation of Principia to German – published in 1988).

Ed’s position is that the real physical (Nature’s) laws reflect cause and effect in the form of geometric proportionality. The most fundamental being E/p=c, where E is energy, p is momentum and c is velocity – a proportionality coefficient, i.e. a constant associated with space over time.  This view is in line with the Poynting vector understanding of electromagnetism, also accepted by Heaviside in his notion of ‘energy current’. It even is the basis of Einstein’s E/mc = c.

The diversion from geometric proportionality towards arithmetic proportionality was due to Leibniz and his principle of “causa aequat effectum“. According to Ed (I am quoting him here)  – “it is a principle that has nothing to do with reality, since it implies “instantanity” of interaction, that is, interaction independently of “real space” and “real time”, conflicting with the age-old natural experience expressed by Galileo that “nothing happens but in space and time” “. It is therefore important to see how Maxwellian electromagnetism is seen by scholars. For example, Faraday’s law states an equivalence of EMF and the rate of change of magnetic flux – it is not a geometric proportion, hence it is not causal!

My view, which is based on my experience with electronic circuits and my understanding of causality between and energy and information transfer (state-changes), where energy is cause and information transfer is effect, is in agreement with geometric proportionality. Energy causes state-transitions in space-time. This is what I call energy-modulated computing. It is challenging to refine this proportionality in every real problem case!

If you want to know more about Ed Dellian’s views, I recommend visiting his site http://www.neutonus-reformatus.de  which contains several interesting papers.