**Yakov Fet **Èíñòèòóò âû÷èñëèòåëüíîé ìàòåìàòèêè è ìàòåìàòè÷åñêîé, Ãëàâíûé íàó÷íûé ñîòðóäíèê,

fet@ssd.sscc.ru**Development of Computer Science in Siberia****Abstract**

**The knowledge on formation and development of computer and information sciences is of great value. Acquaintance with the historical events and distinguished individuals bringing computer science to the contemporary progress should become an essential component of computer education. In this report some results from our investigations on the history of computer science in Siberia are presented.**

** **

**Keywords:**** **Computer Science, Social Issues, Siberian Branch, Personalities

** **

**1. Introduction**

The establishing of the Siberian Branch of USSR Academy of sciences as well as the creative work of scientists of this new scientific center during the following years was of great importance to the history of computer science in Russia (Soviet Union). Looking at these events in detail one can realize a principal contribution of Siberian scientists to the automata theory, theory of computing systems, parallel and distributed computing technique, theoretical and applied programming, etc.

Each of these subdivisions was represented by a definite scientific school, with a distinguished scientific leader at the head. Together with his students and followers, the leader carried out investigations in the corresponding field.

It is well known that in the ‘60s the Siberian Branch attracted great attention of the world scientific community. It was just because leading Soviet mathematicians — Mikhail Lavrentiev, Sergey Sobolev, Leonid Kantorovich, Guriy Marchuk, Alexey Lyapunov, Andrey Ershov and others moved to Novosibirsk. In the Siberian Branch, from the very beginning, priority was given to the development of computational mathematics, mathematical modeling, computer technology, programming. The latest models of domestic computers have been working here.

The founders of the Siberian Branch believed that all sciences (even the Humanities) can be sufficiently advanced if the newest achievements of the computer science will be mastered. In the very beginning of the Siberian Branch, at the end of ‘50s, Lavrentiev wrote: “Instead of building and testing the real installations, we can now estimate, by using computers, every version of the process changing arbitrary its parameters”.

Thus, we become firmly convinced that during the ‘60s and ‘70s years of the last century the point of concentration of cybernetic research moved to Novosibirsk.

There can be no doubt that successful development of computer science in Siberia is connected with the personality of academician Lavrentiev. He is known as one of initiators of the Siberian Branch, as its President. But one should not forget that it was exactly Lavrentiev who saw Computer Science and Computer Technology in a proper perspective as early as in the end of ‘40s. Still working in Kiev, Lavrentiev sent a letter to Stalin emphasizing the importance of support and development of computer technology. It was Lavrentiev who headed during some period the Institute ITMVT and invited to this Institute Sergey Lebedev. We can assert that thanks to Lavtentiev ITMVT become the origin and glory of Soviet computer technology.

In this report, we intend to present some selected pages from the history of Computer Science in Siberia.

** **

**2. Alexey Lyapunov**

In the history of Russian science, Professor Alexey Lyapunov (1911–1973) occupies a particular place in connection with his activities in defending cybernetics and genetics.

A. A. Lyapunov was a representative of the old Russian nobility which originated numerous distinguished workers of Russian science and culture during 19-th and 20-th centuries. While still a young talented mathematician who already was a hero of the Great Patriotic War and a Professor of the Department of Mathematics at the Moscow Artillery Academy, Alexey Lyapunov headed, in the early ’50s, the struggle for the recognition of cybernetics in the USSR. In those hard times, when dogmatic philosophers denounced cybernetics as a “reactionary pseudo-science”, Professor Lyapunov, in the 1954/1955 academic year organized a Seminar on cybernetics at the Moscow State University. This Seminar attracted, from the very beginning, great attention of different specialists and developed into an all-Moscow and even in an all-Union event. He invited for work in this Seminar and presenting lectures the youth as well as prominent Soviet scientists, and sometimes even foreign guests. During ten years (1954–1964) a total of 121 sessions of this famous “Big” Lyapunov’s Seminar was held.

In 1958, he launched his famous series of collections “Problemy Kibernetiki” (“Systems Analysis”) being the editor-in-chief of it. The total of 41 issues have been published during the period 1958-1984.

The fearless struggle for the new science was crowned with full victory.

Lyapunov was a distinguished mathematician, a specialist in the theory of sets. However, the range of his interests was so widespread that he can be rightfully named a person of encyclopedic knowledge. The known Russian historian of science Modest Haase-Rapoport wrote about Alexey Lyapunov: “Despite the broad spectrum of his scientific interests, Lyapunov's activities in science were always distinguished by professional skill. The biologists considered him a biologist, the geophysicists a geophysicist, the philosophers a philosopher”[1]S.

Beginning from 1961 Professor Lyapunov lived in Novosibirsk and worked at the Siberian Division of Russian Academy of Sciences. This was one of the most fruitful periods of his life. Alexey Lyapunov was an outstanding pedagogue, and a propagandist of scientific knowledge. His interests in this field covered the teaching at all the levels of education, from the primary school to the University.

Dr. Igor Poletayev, one of the Russian Computer Pioneers and close Lyapunov's collaborator wrote: “Scientific truth ever was the subject of his service, and the search of this truth — almost a cult. This unselfish, knightly service to the truth was supplemented by his irresistible personal charm <...> and surprisingly deep and, perhaps, inoffensive and kind humor. Even the controversial opinions sounded from Lyapunov's lips attractive, almost convincing. Every conversation and personal contact with him was an intellectual event and aesthetic experience”.

A.A. Lyapunov was a distinguished teacher and disseminator of scientific knowledge. His interests covered the teaching at all the stages of education, from the university down to the primary school level. Lyapunov’s pedagogic activity reached its highest point at the Novosibirsk Academic Village. Together with M.A. Lavrentiev, he initiated the establishment at the Novosibirsk University of the first “Physico-Mathematical School” in Russia. He also was one of the organizers of Siberian Mathematical Olympiads and Summer Physico-Mathematical Schools.

Aleksey Lyapunov is one of the two outstanding Russian computer scientists honored in 1996 as Computer Pioneers. The IEEE Computer Society stated that “Alexey Lyapunov … founded Soviet cybernetics and programming”. The second Laureate was Sergey Lebedev (1902–1974), the “founder of Soviet computer industry”.

It is known that the IFIP WG 9.7 (History of Computing) established a Program of “Pioneer Days” to recognize contribution of distinguished scientists awarded as Computer Pioneers.

Between October 8 and 11, 2001 an International Conference devoted to the 90-th anniversary of Lyapunov’s birth was held in Novosibirsk. Within the framework of the Conference a Pioneer Day was organized on October 8, 2001 to celebrate Aleksey Lyapunov’s memory. This was the first such event devoted to a Russian Computer Pioneer. At the beginning of the Pioneer Day Session, Dr. Gyozo Kovacs (Budapest) made a brief introduction, describing the international computer community’s tradition of celebrating Computer Pioneers and previous Pioneer Days. Then, Natalya Lyapunova, the scientist’s daughter, presented some reminiscences of her father. She showed the audience Lyapunov’s «Computer Pioneer» medal as well as some IEEE Computer Society documents related to this Award.

** **

**3. Leonid Kantorovich**

Leonid Kantorovich (1912–1986) is one of those brilliant scientists whose lives are inalienable from the 20th century history of Russia. One might say that Kantorovich lived two different lives in science, as a mathematician and as an economist. Kantorovich-mathematician started his studies at the age of fifteen and soon was acknowledged as a leading scientist.

The name of Leonid Kantorovich, his life, his role in the science, and his struggle for his ideas occupy a special position in the history of science of the 20^{th} century.

Kantorovich was born in St. Petersburg, in a family of a physician. He showed his talent very early. He entered the Leningrad University in 1926, being only fourteen. Having graduated in 1930, Kantorovich engaged in teaching activity and active scientific work. In 1932 he was appointed a professor at the Leningrad Institute of Engineers of Industrial Construction and a senior lecturer at the Leningrad University, his alma mater, where he took professorship in 1934 and the degree of a Doctor was conferred on him without a thesis defense in 1935. Kantorovich remained associated with the Leningrad University.

The early blossoming of his talent, the discovery (at the age of 27) of new methods of planning and management, the extraordinary breadth of interests, the uncompromising nature of a fighter, and, at the same time, his modesty and nobility — all these features form the unique phenomenon of Kantorovich.

The mathematical investigations of Kantorovich formed a basis of new important directions in mathematics. At the same time, he is rightfully considered one of the founders of modern mathematical economics, the kernel of which is linear programming which he created. It is a new concept of the economical cybernetics which is highly important because it allows to transform economics into an objective science, thus ensuring most efficient results of economic activity.

Functional analysis plays a special role in Kantorovich’s mathematical activity. Being a classic in this area and an author of the theory of ordered vector spaces, Kantorovich made functional analysis a natural language of computational mathematics

He realized the importance of computer technology at its very dawn and believed that this invention “will influence all human activities as greatly as did book-printing, steam engine, electricity, and radio.”

Kantorovich’s famous book “The Best Use of Economic Resources” published in 1959 faced hostile criticism from Soviet economists and caused much debate which lasted as long as until the mid-1960s, attracting keen interest of foreign scientists. It was the time when his first works on linear programming, translated into foreign languages, became famous and brought him priority and recognition in the West.

Kantorovich is the author of more than 300 scientific works, which encompass an impressively broad range of fields, but are united by his personality as well as by the inherent integrity and mutual association of ideas.

The name of Leonid Kantorovich, his life, his role in the science, and his struggle for his ideas occupy a special position in the history of science of the 20th century. The mathematical investigations of Kantorovich formed a basis of new important directions in mathematics. At the same time, he is rightfully considered one of the founders of modern mathematical economics, the kernel of which is linear programming which he created. It is a new concept of the economical cybernetics which is highly important because it allows to transform economics into an objective science, thus ensuring most efficient results of economic activity.

In 1939 Leonid Kantorovich published a small brochure “Mathematical Methods in the Organization and Planning of Production” containing the discovery of linear programming, a new scientific direction which had an enormous influence on the development of economic science. This fundamental work of Kantorovich gave, for the first time, a mathematical statement of economic problems of planning and suggested efficient methods of their solution.

The new, truly scientific approach to economics suggested by L. Kantorovich was incompatible with the official Soviet ideology. For a long time, Kantorovich’s discovery of linear programming had remained unknown to the West. At the end of the ‘40s, similar approaches to optimization have been independently proposed in the USA. In 1975, he was awarded (together with American scientist T. Koopmans) the Nobel Prize in economics “for the contribution into the theory of optimal use of resources”.

The new, truly scientific approach to economics suggested by L. Kantorovich was incompatible with the official Soviet ideology. Economics was one of those humanities (along with history and philosophy) where the ideological conflicts were most critical and the struggle most tense.

From the side of the dogmatic economists, an open persecution of Leonid Kantorovich followed. During the whole his life, the Nobel Laureate Leonid Kantorovich was forced to struggle against the stupid and absurd opposition of orthodox Soviet economists, while persuading the only purpose — to help his country. The most part of his life Leonid Kantorovich devoted to the democratization of economics in his country, to the application of advanced science for the welfare of mankind.

Kantorovich coordinated a number of specific computing projects, including a nuclear studies project and a project on optimization of blanks nesting in the manufacturing industry. He realized the importance of computer technology at its very dawn and believed that this invention “will influence all human activities as greatly as did book-printing, steam engine, electricity, and radio.” Fascinated with computers, he designed one of the first systems of automatic programming and a number of new computer configurations, some of which were then put into practice [2].

In 1957 Kantorovich was invited to the newly created Siberian Division of the USSR Academy of Sciences and was elected a Corresponding Member of the Academy in economics and statistics. Since then his main works were devoted to economical cybernetics.

**4. Search for Efficiency: Unconventional Siberian Architectures**

Unfortunately, the poor Soviet technology, and the incompetence of the management left our country permanently behind the West in building and using computers.

In the beginning of ‘60s, it was clear to Siberian computer scientists that the only way to build high-performance system had to be in parallel computation.

Let us consider in brief some early Siberian architectural projects.

**4.1. Kantorovich’s Contribution**

The range of interests of Leonid Kantorovich was unusually broad, and he made original and deep contributions to all domains of his various activities.

Being àn outstanding mathematician and author of fundamental mathematical theories, Kantorovich also paid considerable attention to the technical realization of complicated computational processes.

As early as the ‘40s, before the advent of electronic computers, Kantorovich successfully used tabulating machines fîr scientific calculations. Íå constructed at the Leningrad Branch of the Mathematical Institute of the USSR Academy of Sciences what would now be called à “multiprocessor parallel computing system” made of tabulators. With this system, the tabulation of Bessel functions bó à special global program was carried out simultaneously for 121 functions.

Later, Kantorovich suggested enhancing the computational capabilities of tabulators bó attaching what àre now called “specialized processors”. One such processor, designed for calculating functions, was created in the late ‘40s.

The concept of large-block organization of computational processes advanced bó Kantorovich in the early ‘50s and developed later in numerous publications bó him and his collaborators constituted his important contribution to computer science. Later on, some of the ideas of the large-block approach were developed in such programming languages as APL, PL-l, Algol-68, etc.

The large-block system with its operand files and dedicated bulk operations opens wide possibilities for new architectural solutions. These include, in particular, various forms of simultaneous processing of mànó elements or quantities. Thus, in organizing arithmetical operations în quantities, it is natural to use independent parallel processing of all components.

The idea of attached units “enhancing” computational possibilities of computers was formulated in its general scope in [3], where à computing system was proposed that consisted of à universal computer of conventional architecture and à small specialized computer designed for somedefinite kinds of bulk processing. It was assumed that the universal machine singled out large-block operators in the program and transferred them for execution to the attached unit. The high performance of the attached processor was obtained bó exploiting peculiarities of various operators and operands exhibited bó the architecture of the specialized small computer. Òî get the necessary adaptability and to enlarge the set of operations of the attached processor, microprogramming control, and à variable data format were used; for connection to the host computer à special interface unit was designed.

In the early ‘60s at the Institute of Mathematics of the Siberian Division where Kantorovich worked at that time, à project had been developed under his direction of an attached unit of this kind, which was called the “Arithmetic Màshine” (ÀÌ) and was intended primarily for speeding up the solution of problems in linear algebra and linear programming.

À pilot ÀÌ computer implemented in 1967–1968 was in operation at the Computing Center of the Siberian Division. For vector and matrix operations, its gain in speed, compared with universal computers of the same technological base, was one order. The ÀÌ computer seems to have been one of the first pipeline vector processors, and thus à prototype of modern supercomputers.

**4.2. Homogeneous Computing Systems**

In 1962, in Novosibirsk, Edward Yevreinov suggested so called parallel *Universal Computing Systems (UCS) *with programmable structure[4]. The main features of UCS were:

- the basic element of UCS is à general purpose computer (Elementary Machine, ÅÌ);

- the UCS has à homogeneous structure, that is, it consists of identical, equally connected EMs;

- the number of EMs in the system ñàï be changed;

- the instruction set, memory size and word length of àn ÅÌ can a1so be changed.

It was proposed to distinguish the UCSs according to their topology as one-, two- and multi-dimensional; according to the type of exchange between EMs: parallel, sequential, and parallel-sequential; according to the spatial arrangement of EMs: concentrated and distributed.

In the Yevreinov’s concept two leve1s of organization of parallel computing systems were considered: the *macrostructural *which has båån briefly described above, and the *microstructural *concerning the inner structure of the elementary machines.

Íåãå again à homogeneous approach was again proposed, based on so called *Homogeneous Computing Media **(**Í**C**Ì**).*

The main properties of the HCM are: homogeneity; short-range interaction; universality of the cells; possibility of setting each cell to implement ànó function from the chosen universal set.

According to Yevreinov, the HCM should be manufactured in à single technological process, like some “computing tissue”, getting the required “pattern” at the last stage of production bó means of appropriate configuring.

The main idea of homogeneous media was *embedding *of logical nets, that is, realization of arbitrary automata, into à planar homogeneous structure shaping the cells in a corresponding manner.

In some sense, the ideas of Yevreinov anticipated bó far the present state of computer science and outlined most of the fundamental problems of development of high-performance computing systems.

**4.3. Distributed Functional Structures**

Most of the cellular automata models (including Yevreinov's ÍÑÌ) are universal. They can realize arbitrary functions and algorithms, and the synthesis of necessary logical structures proceeds using classical automata theory techniques. Unfortunately, most specific functions will incur time and hardware redundancy when implemented in this way.

*Specialized homogeneous structures*, which immediately màð algorithms into circuits, represent àn alternative to the universal ones. In these structures, the given algorithm is simulated bó signal propagation through à specialized logical net. À classical example of such structure is the content-addressed, or associative memory with its special basic operation of “equality search”. Other specialized structures realizing other basic operations have emerged as well.

In 1971, à specialized cellular array (called *α-structure*) having the basic operation of “extreme search” was proposed in Novosibirsk. Later în, numerous arrays have båån designed implementing various basic operations (threshold searches, nearest neighbor searches, compression, etc.). Arrays of this type have båån called *Distributed** Functional Structures *(DF-structures) [5].

Àn important feature of the DF-structures is their multifunctionality. Thus, àn α-structure can be efficiently used not only for extreme selection, but also as an associative memory, à programmable logic array, àn interconnection network, etc.

The conception of DF-structures allows to design efficient parallel accelerators for diverse computer architectures. Indeed, the modern technology allows to implement distributed functional arrays of sufficient size, which can become à new type of VLSI product, *C**ellular Microprocessors. *

**Conclusion**

The Siberian Branch was conceived, from the very beginning, as a strong mathematical and cybernetical scientific center. During a certain period, the Novosibirsk Academgorodok was a kind of a capital of Soviet Computer Science.

Turning back to the history of formation and development of computer science in Siberia, we can suppose that it was not surprisingly that just here, in the Siberian branch of the RAS, recently an initiative came in existence of exploring the history of computer science. During several years, we have published (in Novosibirsk, as well as in Moscow) a series of scientific volumes on the history of Russian Computer Science. Several topics from these books have been presented in this paper.

To-day, our investigations are in progress.

**References**

1. Aleksey Andreevich Lyapunov / Edited by N. Lyapunova and Ya. Fet. — Novosibirsk: Scientific Publ. Center of

RAS, 2001. — 524 pp. — (In Russian).

2. Leonid Vital'evich Kantorovich: a Man and a Scientist. Vol. 1 / Edited by V. Kantorovich, S. Kutateladze, and

Ya. Fet. — Novosibirsk: Scientific Publ. Center of RAS, 2002. — 544 pp. — (In Russian).

3. L.V. Kantorovich and Ya.I. Fet. Computing System Comprising a Universal digital computer and a small digital

computer. / USSR Inventor’s Certificate No. 172567, 1963.

4. Yevreinov E.V. and Kosarev Yu.G. High-performance homogeneous universal computing systems. Novosibirsk:

Nauka, 1966. — (In Russian).

5. Ya.I. Fet. Parallel processing in cellular arrays / Tounton, England: Research Studies Press, 1995. — 196 pp.