заключение
экологические модели становятся в настоящее время обычным ра- бочим инструментом при проведении широкого спектра исследований живой природы от разработки чисто утилитарных природоохранных ме- роприятий и экологических экспертиз до теоретических исследований.
Широкое распространение некогда экзотического метода в сочетании с бурным развитием компьютерных технологий порождает трудности мето- дологического и даже философского порядка. это связано, в первую оче- редь, с проблемой идентификации модели. Какую модель следует считать правильной и пригодной для практического прогнозирования, а какую мо- дель следует забраковать? К сожалению, универсального ответа на этот во- прос, возникающий почти при каждом модельном исследовании, нет. для каждого конкретного случая применения достаточно сложной компьютер- ной или аналитической модели следует оценивать степень достоверности, исходя из реальной степени изученности моделируемого объекта и целей построения модели. замечено, что во многих случаях простые модели об- ладают лучшими прогностическими качествами, чем сложные, в которых стараются учесть как можно полнее все наличные сведения об объекте ис- следования.
однако область применения компьютерных экологических моделей да- леко не исчерпывается определением допустимых квот вылова рыбы или отстрела промысловых животных, оценкой возможного экономического ущерба от поступления загрязняющих веществ в природные экологиче- ские системы. экологическая модель уже давно применяется как средство обучения, подобно тому, как применяются имитационные тренажеры при обучении управлению самолетами или космическими аппаратами. Нако- нец, модель – это средство научного поиска, средство для проверки гипотез об устройстве окружающего нас мира. это, по меткому выражению воль- фганга Грима (Grimm, 1994), «free style models» – модели, предназначен-
394 ные для ответа на вопрос: «А что будет, если предположить, что объект исследования устроен так, как я себе это представляю?». Единственное требование для такого моделирования заключается в том, чтобы иссле- дователь умел изложить свое представление об объекте исследования на языке, понято компьютеру, иными словами, создать соответствующую программу. все сказанное об экологическом моделировании относится и к моде- лированию эволюционному, с той существенной разницей, что исходные данные крайне бедны, а иногда и просто отсутствуют. особенно это каса- ется моделировании макроэволюции. Так называемая «неполнота пале- онтологической летописи» ставит эволюционные модели в положение недоказанных или слабо доказанных гипотез. однако другого способа реконструкции эволюции животного и растительного мира на земле кро- ме моделирования, просто не существует. другое дело, что большинство эволюционистов пользуются вербальными моделями, проверка истинно- сти которых встречает несравненно большие трудности, чем проверка ис- тинности компьютерных моделей. в этом, собственно, и заключается весь смысл эволюционного моделирования. литератураАлимов А. Ф. элементы теории функционирования водных экосистем. СПб.: Наука, 2000. Алимов А. Ф., Умнов А. А. Модель популяции амфиподы Gammarus lacustris // Журнал общей биологии. 1989. № 50 (5). С. 673–681. Астраханцев Г. П., Меншуткин В. В., Петрова Н. А., Руховец Л. А. Моделирование экосистем больших стратифицированных озер. СПб.: На- ука, 2003. Математические модели в экологии. Библиографический указатель отечественных работ/Под ред. А. д. Базыкина; вИНИТИ. М., 1981, 224 с. Баранов Ф. И. К вопросу о биологических основаниях рыбного хозяй- ства// Известия отдела рыболовства и научно-промысловых исследований. Петроград, 1918. С. 84 – 128. Берг Л. С. Труды по теории эволюции. Л.: Наука, 1977. 387 с. Винберг Г. Г., Анисимов С. И. Математическая модель водной экосисте- мы // Фотосинтезирующие системы высокой продуктивности. М.: Наука, 1966. С. 213–223. Винберг Г. Г., Меншуткин В. В. значение математического моделиро- вания для разработки научных основ рационального использования био- логических ресурсов пресных вод // Проблемы долгосрочного планирова- ния биологических исследований (зоология). Л.: Наука, 1975. Галицкий В. В. Компьютерные квазитрехмерные модели дерева и со- обществ деревьев. Анализ динамики конкуренции сообщества. Пущино, 2003.
395
Грабовский В. И. Клеточные автоматы как простые модели сложных систем// Успехи современной биологии. 1995. Т. 115 (4). С. 412 – 418.
Гринченко С. Н. Системная память живого (как основа его метаэволю- ции и периодической структуры). М.: Мир, 2004. 512 с.
Жаков Л. А. Формирование и структура рыбного населения озер Северо- запада СССР. М.: Наука, 1984.
Заде Л. А. Тени нечетких множеств // Проблемы передачи информа- ции. 1966. Т. II. вып. 1. С. 37 – 44.
Иванищев В. В. и др. Имитационное моделирование природной систе- мы «озеро-водосбор» (Севан)/ ЛИИАН. 1987.
Игнатьев М. Б. Голономные автоматические системы/ АН СССР. М.-
Л., 1963.
Игнатьев М. Б. Адаптационный максимум// Сисмтемный анализ и принятие решений: словарь-справочник. М.: высш. шк., 2004.
Игнатьев М. Б. Семиблочная модель города для поддержки принятия решений// Компьютерные модели развития города: Тр. семинара. СПб.:
Наука, 2003. С. 40–45.
Игнатьев М. Б. диплом № 25-S на открытие в области кибернетики и системного анализа. 2005, с приоритетом от 28 июня 1963 г.
Казанцева Т. И. Балансовая модель мелкого высокоэвтрофного озе- ра // Журнал общей биологии. 2003. № 64 (1). С. 128–145.
Казанцева Т. И., Смирнова Т. С. зоопланктон центральной части Ла- дожского озера (имитационная модель) / ИэФИБ. СПб., 1996.
Жаков Л. А., Меншуткин В. В. Применение математического модели- рования в исследованиях по динамике численности окуня: докл. Х конф. по биологии водоемов Прибалтики. Минск, 1963. С. 104–105.
Крогиус Ф. В., Крохин Е. М., Меншуткин В. В. Сообщество пелаги- ческих рыб озера дальнего (опыт кибернетического моделирования). Л.:
Наука, 1969. 87 с.
Кулагина О. С., Ляпунов А. А. К вопросу о моделировании эволюцион- ного процесса //Проблемы кибернетики: сб. вып. 16. M.: Наука, 1966.
Левченко В. Ф. эволюция биосферы до и после появления человека.
СПб.: Наука, 2004.
Лекявичус Э. элементы общей теории адаптации. вильнюс: Мокслас,
1986. 274 с.
Ляпунов А. А., Кулагина О. С. Моделирование эволюционного процес- са // Проблемы кибернетики. 1963. вып. 2. С. 34–47.
Ляпунов А. А. об изучении балансовых соотношений в биогеоценозе
(попытка математического анализа) // Журнал общей биологии. 1968.
№ 29 (6). С. 629–644.
Меншуткин В. В. Популяция рыб как конечный автомат // Структура и динамика водных сообществ и популяций. Киев, 1967. С. 165–175.
Меншуткин В. В. опыт имитации эволюционного процесса на вычис- лительной машине // Журнал эволюционной биохимии и физиологии.
1977. № 13 (5). С. 545–555.
396
Меншуткин В. В. Модель экосистемы пелагиали Тихого океана // оке- анология. 1979. № 19 (2). С. 318–328.
Меншуткин В. В., Китаин В. Я., Цейтлин В. Б. эколого-генетическая модель облавливаемой популяции дальневосточного лосося // вопросы их- тиологии. 1989. № 3. С. 399–405.
Меншуткин В. В., Левченко В. Ф. Имитация макроэволюционного процесса на эвМ // Журнал эволюционной биохимии и физиологии. 1987.
№ 23 (5). С. 658–674.
Меншуткин В. В., Медников Б. М. опыт моделирования эволюции ну- клеотидной последовательности дНК на эвМ // Журнал общей биологии.
1977. № 37 (2). С. 198–203.
Миркин Б. Г. Анализ качественных признаков и структур. М.: Стати- стика, 1980. 320 с.
Налимов В. В., Мульченко З. И. Наукометрия. М., 1969. 169 с.
Свирежев Ю. М., Елизаров Е. Я. Математическое моделирование биоло- гический систем // Проблемы космической биологии. 1972. вып. 20. С. 5–40.
Применение математических методов в биологии/ Под ред. П. в. Те- рентьева. Л.: Изд-во ЛГУ, 1960–1964. 194 с.
Тимофеев-Ресовский Н. В., Воронцов Н. Н., Яблоков А. В. Краткий очерк теории эволюции. М.: Наука, 1969.
Beverton R. J., Holt S. J. On the dynamics of exploited fish populations.
London, 1957.
Botkin D. B. Forest Dynamics. N.Y., 1993.
Daunicht W., Salski A., Noehr P., Neurbert C. A fuzzy knowledge-based model of annual production of skylarks//Ecological Modelling. 1993. N 85
(1). P. 67–73.
Doi T. Dynamical treatment of exploitation of aquatic recourses. Dynamic characteristics of single population// Bull. Jap. Soc. of Scientific Fisheries.
1955. N 21 (11). P. 3–22.
Grimm W. Mathematical models and understanding in ecology // Ecological modeling. 1994. N 75/76. P. 641–651.
Grimm W. Ten years of individual-based modelling in ecology: what have we learned and what could we learn in the future// Ecological modelling.
1999. N 115. P. 129–148.
Goldberg D. E. Genetic algorithms in search, optimization, and machine learning. Reading, MA: Addison-Wesley, 1989.
Gould S. J., Eldredge N. Punctuated evolution: the tempo and mode of evolution reconsidered// Paleobiology. 1977. Vol. 3. P. 11–26.
Kaufman A., Gupta M. M. Fuzzy Mathematical Models in Engineering and
Management Science. Amsterdam: North Holland, 1988.
Larkin P. A., Hourston A. S. A model for simulation of the population biology of Pacific Salmon // J. Fish. Res. Bd. Canada, 1964. N 21 (5). P. 1245–1265.
Malthus T. R. An Essay on Population. London, 1803.
Meynard-Smith J. Models of evolution// Proc. Royal Soc. Ser. B. London,
1983. Vol. 219 (1216). P. 315–326.
397
McMillan W. O., Weight L. A., Palumbi S. R. Color pattern evolution, assortative mating, and genetic differentation in brightly colored butterflyfishes (Chaetodontidae) // Evolution. 1999. Vol. 53. N 1. P. 247 –
266.
Nielsen R., Slatkin M. Likelihood analysis of ongoing gene flow and historical association // Evolution. 2000. Vol. 54. N 1. P. 44 – 56.
J
ørgensen, S. E., Halling B., Nielsen S. N. (ed.). Handbook of environtment and ecological modelling. Lewins Pub, 1995. 538 р.
Stanley S. M., Signor P. W., Lidgard S., Karr A. F. Natural Clades Differ
From “Random” Clades: Simulations and Analyses//Paleobiology. 1981. Vol.
7 (1). P. 115–127.
Takimoto G., Migashi M., Yamamura N. A deterministic genetic model for sympatric separation by sexual selection // Evolution. 2001. Vol. 56 N 6.
P. 1870 – 1881.
Urbanek A., Uchmanski J. Morphogenesis of uniaxiate graptoloid colonies – a mathematical model // Paleobiology. 1990. Vol. 16 (1). P. 49–61.
Vinogradov M. E., Menshutkin V. V. The Modelling of Open-Sea ecosystems
The Sea: Ideas and observations on the progress in the study of seas. N.Y.:
J.Whely and Son., 1977.
Wu C.-J. A stochastic simulation study on speciation only sexual selection. // Evolution. 1985. Vol. 39 (1). P. 62–82.
398
ПРИЛОЖЕНИЕ 3
RecuRSive MachineS and coMputing technology
v. M. glushkov, M. B. ignatyev, v. a. Myasnikov, v. a. torgashev
The paper analyzes disadvantages of traditional computers. It shows that partial revision of von Neumann principles fails to provide a leap in the development of computing technology. New principles of program and structural organization of digital computers are offered.
Their name, «recursive computers» (RC), stems from the recursive method of defining their internal language and structure. The main features of their internal language and their tentative architecture are considered, and their capabilities are evaluated.
1. Introduction
More than a quarter of a century has passed since digital computers first emerged. During this period of time, three generations of digital computers have evolved, and their speed, reliability and memory size have increased, while their cost, dimensions and power consumption have decreased.
Yet, the basic principles of digital computer structure and program organization, which were proposed by von Neumann as far back as
1946, remained invariable. These principles include:
low level machine language (commands are elemental operations performed on elemental operands). sequential centralized control of computational process (control is by a single sequence of commands, each providing fulfillment of one operation and passing control to the next command), linear organization of storage consisting of similar series- numbered cells.
These principles provide simplicity of digital computer structure and involve a minimum number of logic (active) elements. Such computers (Princeton type, or von Neumann computers) are known as classical or traditional. As long as logic elements were much more expensive and less reliable than memory elements and digitally solved problems remained simple enough and external devices were few, the above principles were certainly progressive. But now they hamper the development of computing technology.
2. Disadvantages of traditional digital computers
399
Simplicity of traditional digital computer structure results in unjustified complication of software systems, which now seem to reach the upper limit of complexity and still do not satisfy users in many respects. Consider also, that each of the above principles contributes essentially to the complexity of software.
A great gap, for example, between the machine language and the external one is responsible for the emergence of involved translators constituting a major part of any software system. Difficulties related to the development of translators and the large memory sizes required to contain them make software designers prefer less effective languages
(such as Fortran, Algol-60) because of their greater simplicity from the viewpoint of translator construction. As for users of medium and, particularly, smaller computers – they have to manage with curtailed forms of external languages. Especially great difficulties arise in constructing translators for deeply recursive languages, which are most efficient in programming complex tasks.
It is obvious that linear organization of storage is not commensurate with the structure of data and programs for the majority of real tasks.
As a result, one has to introduce into the software rather elaborate systems of dynamic allocation of memory which, as a rule, require either sophisticated processor hardware and considerable internal memory sizes or great consumption of machine time.
The heart of any software system is the supervisor which integrates all digitally solved tasks into a single program and controls the computational process. Great complexity of the supervisor is attributed primarily to the principle of centralized, sequential control employed in traditional computers, since this principle forces the integration of all programs inside the computer into a unified sequence of commands.
A supervisor designer must provide for all situations which may happen in the course of computing.
Another substantial disadvantage of traditional digital computers is that their throughput obviously depends on the speed of their components. When developing super high-speed components for supercomputers capable of performing tens of millions of operations per second, we are approaching the fundamental limitation, namely, the final velocity of electromagnetic wave propagation. It is felt, therefore, that computers of the Princeton type have practicably exhausted their potentialities of raising throughput. As to increasing throughput by paralleling computational processes, it is almost impossible to do so on a large scale (except for some particular tasks), as long as the first two
400
von Neumann principles remain in force. This is because operational complexity and time consumption of the supervisor and the system of dynamic memory allocation grow in proportion to the number of computational processes performed at a time.
The present rapid advance of microelectronics and the emergence of large scale integrated circuits result in the cost and reliability of logic elements being near those of memory elements; hence, there are grounds to revise the von Neumann principles, as the minimum number of logic elements no longer leads to the minimum cost of the computer
(this is especially true if the software cost is taken into account).
3. Revision of von Neumann principles
Most papers on organization of non-traditional computers revise only one of von Neumann’s principles (namely, the first one).
For instance, [1] gives theoretical reasons for the necessity of the transition to high level internal language and to advanced systems of interpretation. Efficiency of such a transition is proved by the experience gained in designing both small machines (МИР [2]) and large machines (SYMBOL [3]). It should be noted, however, that raising the internal language level more often amounts to just implementing in’ hardware some of the modern medium-level algorithmic languages
(Algol-60, Fortran). As for smaller machines, one has to develop still simpler languages, usually oriented to calculation tasks. The purely sequential, nature of the above languages (and the same is true, by the way, for the overwhelming majority of the other modern algorithmic languages) limits the possibilities of accelerating the interpretation processes through paralleling them on a wide scale. Therefore, for the sake of preserving computer throughput, one has to limit the depth of interpretation which, in turn, does not allow one to simplify essentially the internal software system.
The principle of sequential control of the computational process has remained inviolable over the entire period of computing technology development. Even when developing highly parallel computer systems, designers parallel the very computation through local changes of the internal language level. For instance, the ILLIAC-IV computer employs numerical matrices as operands. In the STARAN-IV computer, we see that for any two-place operation, one operand is an elemental number
(or word), while the other one corresponds to a multitude of numbers
(words) possessing some common tag. In the STAR-100 computers, the sequences of elemental commands are integrated into operators, employed for one-dimensional numeric or symbolic arrays, with
401
the commands carried out in the series-connected processors. In all these cases, a partial raising of the machine language level does not facilitate, but even complicates, the problem of software system organi- zation.
Efforts taken over the last decade to develop computers with decentralized parallel control have not resulted in real computers, primarily because only the computer structure was subject to change, while principles of program organization remained traditional. As a result, programming became sharply more complicated for simple tasks, not to speak of powerful software systems.
So, von Neumann machines apparently fail to meet the demands of modern computing technology. However, no convincing alternative to these machines has been proposed as yet. The long life of Princeton type computers is attributed to a profound matching of their structural and program organization and to the mutual harmony of the von Neumann principles. Any partial revision of these principles inevitably involves contradictions between machine structure and computational process organization. Therefore, this way would hardly lead to creation of a viable computer model capable of coping with all tasks modern computing technology may face. Only complete replacement of all the von Neumann principles by a new system of principles, affording as full matching of computer structural and program organization as in traditional machines, can bring success.
Following is a description of these new principles and the appropriate type of computers. Their name, recursive computers (RC), reflects both the structure of their internal relations and the structure of the machine language.
4. Principles of recursive computer organization
The first principle consists of limitless level of machine language; that is, language structure does not limit basically the number of language levels and complexity of operators (commands) and operands.
For instance, operands may be represented not only by numbers or sets of characters as in traditional machine languages, but also by vectors, numerical or symbolic matrilines, multidimensional arrays etc. The potential infinity of internal language levels defines its recursive nature unambiguously. Such a language allows one to define all the elements of the lowest level (their number is always finite) and to set recursive rules of transfer from any level elements (except the lowest ones) to the previous level elements. A specific form of RC internal language will be discussed later.
402
The recursive nature of the internal language provides compact representation of both application and service programs, essentially simplifies the structure of translators from any external languages, affords effective programming directly in a machine language, and brings about conditions for programming in languages close to natural ones.
Such a language, however, is totally incompatible with sequential control of the computation process. In fact, the higher the level of some program element, the more time is spent on its interpretation as computation is carried out at the lowest level. So, with the number of internal language levels growing, the fraction of total machine operation comprising control and interpretation processes increases, and efficient throughput drops accordingly. For faster execution of the whole program, it is necessary to provide extensive paralleling of control processes making transfers to succeeding program elements
(commands) without waiting for the end of the previous ones. However, if these elements are complex enough, it is next to impossible to define their sequence of execution in advance. Therefore, the principle of centralized sequential control should be replaced by the principle of decentralized recursive parallel control of the computation process.
The second principle of RC organization is that all program elements for which operands are available are to be executed. Readiness of some operator (program element) for execution is checked only if all higher level program elements comprising the given operator are in the state of execution (interpretation). Such a method of control provides efficient dynamic paralleling of computation processes and permits the removal of interruption processing programs from the software system, since interruptions make no sense in this case; in general, many supervisor functions become unnecessary. Besides, the very process of programming in a language (either internal or external) which employs operands for defining the program execution procedure becomes essentially simplified and, less sensitive to the programmer’s errors.
The principle of recursive parallel computation process control is incompatible with the linear organization of storage, primarily because of the need for simultaneous and independent access to different parts of the storage. Furthermore, the problem of dynamic storage allocation becomes essentially unsolvable in this case. In order to fit RC memory structure to the above principle of control, it is necessary to provide an opportunity for program integration of the memory elements into tree-like or net-like multilevel configurations
403
corresponding to the structure of data and programs represented in the RC internal language. Moreover, all RC internal memory can be divided program-wise into independent parts of an arbitrary size, with each of them corresponding to a certain program element. The number of these parts is dictated, on the one hand, by the number of processors within a RC and, on the other hand, by the number of program elements ready for execution.
The third principle of RC organization is that memory structure should be re-programmable in order to convert the structure of data and programs represented in the internal language. Such a storage organization removes most problems of dynamic storage allocation.
Computers operating on the above principles could have far more forms of structural organization than traditional computers, which usually differ from each other only very slightly. Nevertheless, all machines in question have a common feature, which is an opportunity for unlimited paralleling of computation processes (including control processes).
Therefore, these machines could comprise any number, however large,- of processors and storage units. As to infinite, non-uniform structures – they can be well described with recursive definitions. Initial elements of the structure, namely zero rank elements, are described, for this purpose, in a usual way. These elements are used to construct first rank machines, which would be elements for constructing second rank machines, which in their turn would be elements of third rank machines, and so on. If the process of transfer from n-rank machines to n+l-rank machines is defined unambiguously for any n_>0, then the structure of such machines is recursive.
The fourth principle of RC organization is that, basically, there are no limits to the number of machine elements. This offers one an opportunity to design a large RC family ranging from small machines to super-systems and nets of computers, with common construction, technologies and programs. What is more, a great number of functionally equivalent elements available in a machine allows one to radically solve the problem of availability, since failures of certain RC parts would somehow affect parameters but not disable a machine.
Recursive structure rigidly defines connections of elements in a machine. At the same time, establishing certain fixed links does not allow one, in the general case, to fit the structure of programs and data to the machine structure. This inevitably results in more complicated software. To obtain the needed match, one has to incorporate switching elements in the RC providing flexible, reprogrammable connections
404
between various RC elements, in the way it is done in modern, automatic telephone exchanges. Thanks to this, RC structure could be adapted to the structure of tasks the machine solves.
The fifth principle of RC organization consists of a flexible, reprogrammable structure. Any group of RC elements, possibly remote from each other, with at least one processor among them, can form a relatively independent computer while executing a program.
Spatially sharing various programs in a RC permits the removal of unexpected effects of programs on each other. Replacement of time sharing by space sharing would make the user a full master of a RC part allocated to him. Not only could he use any RC commands, but he could also insert any commands of his own, even in cases when these commands coincide in their identifications and code with RC routines, but have different meanings. This feature would improve
RC versatility (compared to traditional computers), and serviceability would increase accordingly.
One naturally can judge to what extent the above principles are effective after they are implemented in actual computers. To gain an idea about recursive machine capabilities, let us consider one of the possible RC versions. The framework of this small paper makes it practically impossible not just to describe a RC in detail, but even to present all its essential features. Therefore, the following part of the paper is, unfortunately, of rather fragmentary nature.
5. Basic features of language of recursive machines (LAREC)
As was mentioned before, RC machine language is multilevel. There are 5 types of LAREC elements.
The initial level of the language comprises the following elements:
variables, lists, microprograms, operators, arrays (LAREC elements of higher levels).
From these, one can establish files, catalogs and blocks.
Any LAREC element consists of a local number, a description and a body. The local number of an element is, to a certain degree, equivalent to its address within a higher level element which directly contains this element. Multilevel language structure makes it possible to restrict local numbers to one byte and to a half byte for operators and some forms of variables. This means that any LAREC element can directly comprise up to 256 elements of lower levels.
405
The description of any LAREC element defines its type and form and contains, depending on the description’s form, a number of parameters defining the internal structure of the element body.
A variable is a LAREC element whose body consists of an ordered population of data which can be considered in the program as an entity (operand for some operator). A RC uses three main varieties of variables: characters, words and lines. Besides, any user of the
RC can define up to 256 additional varieties of variables (vectors, matrices, polynomials etc.). The form of a variable also characterizes the elements of its body: numbers may be complex or real, decimal or binary, integers or fractions, fixed or floating point, with fixed or variable format. Apart from numbers, elements of a variable’s body may be represented by words consisting of bit or byte characters and by names. One byte is allotted to define any of the main parameters of a variable (formats and word orders, amounts of words within a line). However, there is an opportunity to increase the parameter which characterizes the number of words in a line to two bytes. Thus, a line may comprise 65 536 words. Formats and order (for floating point numbers) are measured in half-bytes. Thus, the maximum size of words within a variable is 128 bytes.
A list is a LAREC element whose body, depending on the list’s form, consists of a set of couples: NAME-NUMBER, NAME-NAME,
NUMBER-NUMBER, NUMBER-NAME. Lists allow correspondence of the numbers of LAREC elements to their names (external or internal identifiers). Besides, names or numbers of LAREC elements may be changed by means of lists. For instance, during transfer of a variable from one LAREC element to another, the variable’s local number is changed. Instead of local numbers of elements, lists use global numbers representing a sequence of local numbers of those LAREC elements which comprise an element sought for. Notice that the first number in this sequence is the local number of the LAREC element directly included in that very element which comprises the list itself, while the last number is the local number of the element sought for.
Formats of names and numbers may be defined both for the entire list and individually for each, list element. One byte is allotted for definition of formats or a number of list elements, with an opportunity of expanding to two bytes.
A microprogram is a LAREC element whose body is an ordered sequence of standard format microcommands. Description of a microprogram includes only a number of microcommands constituting
406
it. The purpose of microprograms will be discussed after the other machine language elements are defined. An operator is a LAREC element whose body contains one or two (depending on the operator’s form) local numbers of those LAREC elements which are directly in the same element as the operator. Operators are the simplest elements of the program represented in RC internal language. They correspond, to a certain degree, to traditional computer commands, since local numbers included in the operator’s body are addresses of operands.
Also, the operator’s form defines the type of operation which is to be performed on the operands. However, in traditional machines, each command is associated with only one microprogram, while in RC, each operator is fitted with a variety of microprograms. A concrete microprogram is defined from this variety in accordance with operand forms. For example, one and the same multiplication operator may be associated with multiplication operations such as number by number (binary or decimal, integers or fractions, floating or fixed point), number by line, line by line (multiplication of the respective elements of lines, numbers of elements in operands being equal) and file by file of different dimensions (resulting in a new array whose elements are products of corresponding elements of initial files). The same operator is used both to perform the «AND» operation on binary digits and to integrate two symbolic words into one word inside which a multiplication sign is placed. If one or both operands contain names
(not included in lists), then by these names one must find variable numbers and symbols, but not names. Only then can one determine which operation from the operator’s work possesses the same local number as the operator does itself.
An array is any LAREC element whose body consists of LAREC elements of lower levels. An array is called one-dimensional if there are no arrays among its elements. Otherwise, it is called multidimensional.
A file is an array whose elements are only variables and/or files.
A catalog is an array whose elements are only lists and/or catalogs.
A block is an array whose elements include either a block’s name or whose body consists of only blocks and/or operators. Each block
(like each operator) has a 4-digit number. However, different units and operators may be included with the same numbers in an array block only if their simultaneous operation is impossible due to the structure of the block element internal links. Thus, the number of
407
different elements of array blocks cannot be significantly more than
16. The block body normally includes: a list of input addresses, a list of output addresses (both have the form NUMBER-NUMBER), a list or name catalog (the form NUMBER-NAME), as well as a file of initial conditions and constants, a file of internal variables and an array of microprograms. The last three arrays together with array blocks can be replaced by a block name. Such a block corresponds to the procedure, and in order to carry it out, one has to find the respective arrays by the name.
Any block has input and output ports (up to 16 of each type). The list of input addresses correlates each input port of a block with the output of an adjacent block. The list of output addresses correlates the output port of an internal block with such an output port. Lists of addresses mainly define program structure.
The name list puts names in correspondence with some output ports of internal blocks (including the block with number zero). The name lists provide agreement between external names of program variables and their machine addresses. Besides, the programmer (or translator) can have access by means of the name list to those program elements whose addresses are unknown.
The internal variable array contains output and intermediate results of the block’s work. This array is empty before the start of work of the previously operationless block.
The microprogram array contains microprograms providing the realization of internal blocks and operators included in a given block.
Before the start of block operation, this array is empty and is gradually implemented in the course of the block operation. However, if the programmer wants to employ his own method of realization of standard operators (blocks) or to give different meaning to these operators
(blocks), he can introduce his own microprograms into his program, and the operators (blocks) employed by him would be interpreted in accordance with them.
There are several forms of blocks, differing in the way of execution: free block, block-function, block-compiler, sequential block.
A free block permits an arbitrary order of execution of constituent blocks and operators, depending on the readiness of operands, availability of ready microprograms for operators and availability of free processors and memory modules.
A block-function begins execution only when microprograms are found for the operators included either directly in the block
408
or in internal blocks. Each operator is correlated with a particular processor, and all these processors are interconnected according to the block structure. This block implements parallel computation the way it is done in analog computers.
A block-compiler also starts computation only when microprograms are found for all its constituent operators. However, these microprograms are compiled into a unified microprogram. And for implementation of the block, only one executive processor is allotted, in which all the operators are executed sequentially. A block-compiler corresponds to traditional methods of execution of programs in computers.
Only one element (block or operator) of an internal block array can be executed in a sequential block at any given moment, after which a successive element starts execution. Operators which are equivalent to transfer commands and are included in the number of the block element permit a change in the natural order of the block element sequence.
Among RC operators are those that provide replacement of any block element (except internal block arrays) by their operands. Thus, there is an opportunity to change external relations of the block, variable names, initial conditions and running values of variables during the course of executing the program.
Among microprograms, one can distinguish: executive, manager
(administrator), supervisory, input-output and check microprograms.
Executive microprograms correspond to concrete implementations of operators. Administrators provide block operation with each form of block associated with a corresponding administrator. Supervisors allocate RC resources within program blocks, i. e., memory modules, processors, linking elements and external devices. Input-output microprograms provide control of selector and multiplexor channels.
And, finally, check microprograms, monitor correct execution of the program, localize and disengage faulty RC elements and recover distorted parts of the program.
6. Architecture of recursive machines
Recursive machines by their essesence are multiprocessors. However, if we take modern computer processors and memory units (with a capacity of several К bytes) as basic elements for the construction of a
RC, we would see that a RC even of second rank, if not first, reaches, in terms of costs, the level of computation of supersystems, while being still far behind conventional computers in terms of throughput. We are interested in using the recursive philosophy to construct not only
409
supersystems but also, and to a greater degree, medium- and small-size computers, which form the major part of computer stock. Therefore, one should choose the simplest and cheapest devices as the basic elements of a RC. It is reasonable also to use in processors a sequential method of processing data, especially because in this case data formats can be changed over a wide range. Besides, the fifth principle of RC organization unambiguously specifies sequential transmission of data between RC elements; otherwise, the element connection system becomes practically infeasible. It should be noted that the very structure of RC internal language, though it looks complicated, allows us to simplify RC processors.
Analysis shows that a processor providing execution of any RC machine language elements can be implemented in the form of LSI circuits of MOS transistors with an integration level of some thousands of components. This processor (microprocessor, to be more exact), is as simple as a primitive calculator. Presently, LSI circuits for calculators cost less than $10, and their cost decreases with every passing year.
Unlike microprocessors, which are much simpler than their traditional protopypes, RC internal storage units become essentially complicated from the functional viewpoint. In particular, it is quite necessary to use an associative mode of data retrieval, without which it is practically impossible to implement the recursive parallel method of control. Besides, it is desirable to have an opportunity to organize buffers and boxes in storage without direct involvement of microprocessors. The second cause of RC storage complication lies in the fact that very small memory units, modules, should be used as basic elements in order to be in line with the third principle of RC organization. But as this takes place, the necessary equipment to control storage naturally increases. On the other hand, absence of sophisticated address decoders offsets, to some extent the increase of equipment in RC storage. Furthermore, the demand for storage element speed becomes significantly less due to the sequential input and output of data and the absence of buses which formerly passed through a great number of storage elements. Moreover, the functional complexity of RC storage calls for charging it with quite a number of functions which are performed by processors in traditional computers.
Hardware expenses of RC memory, for 32-byte modules, increase about 1,5 to 1,7 times costs of traditional memory per bit, implemented in the form of LSI circuits. However, if one takes into account more effective use of RC memory as compared with traditional machines,
410
due to fitting data structure to storage structure, compact writing of application and service programs and wide use of variable formats, then it turns out that hardware expenses for the same tasks with reference to one bit of stored data are less in RC than in traditional machines.
Unlike microprocessors and memory modules, RC connecting elements have no counterparts in traditional machines. These elements (modules), linked up in a switching field, provide automatic retrieval and connection between different RC parts. Besides direct connections, the switching field makes it possible to form branches from main paths, thus constructing tree-like and net-like structures from microprocessors and storage modules. The microprocessor at the main trunk base may control any tree. This main microprocessor may have access either to all the tree elements simultaneously (for example, during associative retrieval) or to a single branch. Each branch has a number equal to a local number of the respective LAREC element. By using a sequence of local numbers, the microprocessor can have access to any specific tree element. Further, the main processor may allow another processor to be switched to any tree branch. In this case, the allotted branch is at the full disposal of another microprocessor till it is needed by the main one again. While the second microprocessor is busy with the branch, it can, in its turn, allow still another microprocessor to be switched to a part of the branch. Thus, a great number of microprocessors can be switched to one tree at a time.
While executing a program, the structure of RC internal relations
(its internal architecture) continuously changes. One branch begins to grow and ramify at the expense of adding the nearest free elements.
Other branches, on the contrary, die off, since released elements
(memory modules or microprocessors) are automatically excluded from the tree. Still other branches pass from one tree to another. As a whole, the internal architecture reflects the structure of tasks under solution, taking into account the recursive structure of the internal language.
RC external architecture is fixed during manufacture of the machine and remains invariable except for the «growth» of the RC due to adding new elements and external devices.
Assume that switching modules (SM’s) have 6 groups of external terminals by means of which these modules are interconnected. Let us construct a switching field from the switching modules in the form of a rectangular parallelepiped with the dimensions.
411
Each of the internal SM’s is connected.with 6 other SM’s, so that all its terminals are engaged. As to peripheral SM’s, they have free terminal groups to which the other RC elements can be switched. If we leave one of the sides measuring 1 x m free and connect microprocessor, memory, and input-output modules to the others, we obtain a RC of the first rank. Qualitative correlations between different elements are defined, depending on the class of tasks which the RC is intended to solve, while the arrangement of elements in the switching field can be chosen arbitrarily. After constructing another switching field in the form of a parallelepiped measuring 1 x m x n and connecting the RC of the first rank to it, we obtain a machine of the second rank. This process may continue to infinity. In the general case, architecture of such a RC can be defined recursively.
Any RC consists of the switching field constructed in the form of a rectangular parallelepiped. One of the sides of this field contains the external RC terminals, while the other sides are engaged with other RC’s (their external terminals) or with RC initial elements
(microprocessors, memory and input-output modules).
A minimum RC, in terms of number of elements, contains two microprocessors, one input-output module and several memory modules, part of which are used for storing microroutines. The internal language of such a RC uses only blocks of a sequential form; i. e., the machine operates in a traditional mode. The first microprocessor operates in an administrative mode, while the second one is in an executive mode. Switching modules are unnecessary in this case, for the external architecture agrees with the internal one. Such a RC is equivalent to a powerful calculator. With storage capacity increased to
25 to 30 modules and a set of operators and standard blocks extended, such a machine is capable of solving complex enough, though not demanding, tasks with high throughput. Further growth of the RC, however, requires the introduction of the switching field into the machine and increasing the number of microprocessors.
Recursive machines offer very effective solution of the reliability problem. By using combined methods of hardware and algorithmic check, one can dependably find any errors occurring in the course of computation. The regular structure of the RC makes it possible to localize the faulty element simply enough. If a SM fails, modules adjacent to it set all links going to the faulty SM to the «engaged» position, and now any routes would be laid to by-pass this module.
Similarly, other types of failed elements are switched off (the SM
412
adjacent to the failed element considers this element engaged and does not deal with it any longer). Switching off failed elements involves no changes in programs and does not affect RC operation. True, the limit characteristics of the RC slightly worsen due to switching off, but this worsening would be noticeable only after at least 5% to 10% of all the elements fail. Therefore, large RC’s (exceeding 1 000 elements) practically need no repair over their lifetimes.
7. Conclusion
The five principles of structural and program organization of computers set forth in this paper suggest one common idea,
RECURSIVENESS. In fact, these principles, in a more concise form, sound like this: recursive internal language of machine, recursive parallel method of control, recursive memory organization, recursive external architecture of machine, recursive internal architecture. So, it is natural to apply this term to machines where these principles are implemented and call them recursive.
In traditional computers, all tasks are tailored to a tough machine structure, which is a Procrustean bed, in truth. The «feet» of tasks are cut off, and so are the «heads» – due to introducing lots of limitations, that sometimes emasculate the essence of tasks. The extreme complexity of modern system software is attributed to the same reasons.
The recursive philosophy of computer organization allows flexible reconstruction of machines in accordance with the structure of tasks.
They offer simpler software in many respects, less capacity of working internal memory and lower requirements on the external memory.
Recursive machines consist of a great number of simple elements of small nomenclature interconnected in a regular way. The same elements are used to construct both simple calculators and supersystems. This all favors mass production of RC’s with maximum use of LSI and provides for their economic efficiency.
RC’s provide an effective solution of the reliability problem, removing the need for repair of the machine over its lifetime (till it grows old morally).
The authors hope that a discussion of the recursive machine concept will make it possible to formulate the main problems of computation technology development.
Published in: Proceedings of IFIP Congress. 1974. P. 66. Reprinted with authors’ permission.
V. M. Glushkov, USSR Academy of Sciences Institute of Cyberne- tics, Ukrainian Academy of Sciences, Kiev, USSR;
413
M. B. Ignatyev, Leningrad Institute of Aviation Instrument
Making, Leningrad, USSR;
V. A. Myasnikov, Main Department of Computing Engineering and
Control Systems State Committee of the USSR Council of Ministers for Science and Technology, Moscow, USSR;
V. A. Torgashev, Leningrad Institute of Aviation Instrument
Making, Leningrad, USSR.
414
Содержание
Предисловие .............................................................................
3
введение ...................................................................................
6
Глава 1. Научная картина мира и ее эволюция ............................... 11 1.1. Мифологическая картина мира ......................................... 14 1.2. Механистическая картина мира ........................................ 16 1.3. Неклассическая картина мира .......................................... 18 1.4. Принцип обратной связи .................................................. 20 1.5. Самоорганизация и внешнее управление ............................ 21 1.6. Трудиться – значит улавливать потоки энергии
(работы С. А. Подолинского) ................................................... 34 1.7. Автоматизация и сложность ............................................. 39 1.8. виртуальные наномиры ................................................... 47 1.9. Пример системы с внешним управлением (текущие угрозы террористических атак на авиационные системы и их отражение с помощью внешнего управления) ............................................ 50 1.10. Лингвистический поворот ............................................... 61
Контрольные вопросы ............................................................ 64
Глава 2. Моделирование слабо формализованных систем ................. 66 2.1. Лингво-комбинаторное моделирование и операция поляризации ......................................................................... 68 2.2. Адаптационные возможности сложных систем .................... 71 2.3. Кибернетическая физика .................................................. 80 2.4. Кибернетическая астрономия и астрофизика ...................... 86 2.5. Кибернетическая метеорология ......................................... 91 2.6. Системная кибернетическая биология ................................ 92 2.7. электронный паспорт здоровья на основе компьютерной модели организма .................................................................. 97 2.8. экономическая кибернетика ............................................. 101 2.9. Кибернетическая герменевтика ......................................... 106 2.10. деловая игра «Моделирование города» ............................. 108
Контрольные вопросы ............................................................ 109
Глава 3. Роботы и искусственный интеллект .................................. 112 3.1. Структурирование робототехнических систем ..................... 113 3.2. основные уровни управления поведением робота ................. 118 3.3. Лингвистический подход к анализу уровневой структуры системы управления роботов ................................................... 120 3.4. Робот как многоцелевая система с избыточностью ................ 125 3.5. основные элементы роботов-манипуляторов ....................... 128 3.6. Информационные системы роботов .................................... 144 3.7. Системы обработки информации ....................................... 162 3.8. Построение второго уровня управления манипулятором ....... 164 3.9. Уровни управления шагающей машиной ............................ 167 3.10. Роботы для игры в футбол ............................................... 183
415 3.11. Проблемы создания роботизированного автомобиля для повышения безопасности движения ................................... 184
Контрольные вопросы ............................................................ 201
Глава 4. вычислительные системы и сети ...................................... 202 4.1. эволюция архитектуры вычислительных систем ................. 203 4.2. Рекурсивные вычислительные системы .............................. 216 4.3. Технологии защиты информации ...................................... 234 4.4. Технологии системы-на-кристале ...................................... 235 4.5. закон Амдала ................................................................. 236 4.6. Мир как модель внутри сверхмашины ................................ 238
Контрольные вопросы ............................................................ 241
Глава 5. Миры реальные и виртуальные ........................................ 242 5.1. Многоагентные обучающие системы – современный подход к образованию ....................................................................... 243 5.2. открытое образование ...................................................... 252 5.3. дистанционное обучение .................................................. 255 5.4. виртуальные образовательные среды ................................. 259 5.5. Интеллектуальный и программный агенты ......................... 260 5.6. Технологии виртуальных миров в театре ............................ 269 5.7. Многовариантная история Петербурга ............................... 278 5.8. Репрессированный музей и панорама битвы за Ленинград ..... 284 5.9. Моделирование поля боя .................................................. 290
заключение .............................................................................. 298
Перечень тем рефератов и дипломных работ .................................. 300
основная литература .................................................................. 303
дополнительная литература ........................................................ 303
Приложение 1. Шек-Иовсепянц Р. А., Сабо, Б. в. Уткин Ю. И.
К истории авиационных бортовых вычислительных систем ............ 308
Приложение 2. Меншуткин в. в., Казанский А. Б., Левченко в. Ф. экологические и эволюционные модели ....................................... 374
Приложение 3. Glushkov V. M., Ignatyev M. B., Myasnikov V. A.,
V. A. Torgashev. Recursive machines and computing technology ......... 398
Учебное издание
Игнатьев Михаил Борисович
КИБЕРНЕТИЧЕСКАЯ КАРТИНА МИРА
Учебное пособие
Редактор А. Г. Ларионова
верстальщик С. Б. Мацапура
Сдано в набор 4.10.10. Подписано к печати 29.12.10.
Формат 60
×84 1/16. Бумага офсетная. Печать офсетная. Усл. печ. л. 26,0.
Уч.-изд. л. 26,2. Тираж 200 экз. заказ № 609.
Редакционно-издательский центр ГУАП
190000, Санкт-Петербург, Б. Морская ул., 67
|
Скачать 14.04 Mb.