WO1994015280A2 - Architecture informatique destinee au transfert de donnees parallele dans des langages informatiques declaratifs - Google Patents

Architecture informatique destinee au transfert de donnees parallele dans des langages informatiques declaratifs

Info

Publication number
WO1994015280A2
WO1994015280A2 PCT/EP1993/003636 EP9303636W WO9415280A2 WO 1994015280 A2 WO1994015280 A2 WO 1994015280A2 EP 9303636 W EP9303636 W EP 9303636W WO 9415280 A2 WO9415280 A2 WO 9415280A2
Authority
WO
WIPO (PCT)
Prior art keywords
memory
heap
stack
hinge
pointer
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/EP1993/003636
Other languages
English (en)
Other versions
WO1994015280A3 (fr
Inventor
Robert Milikowski
William Gerard Vree
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
EUROPEAN INSTITUTE OF TECHNOLOGY
Original Assignee
EUROPEAN INSTITUTE OF TECHNOLOGY
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by EUROPEAN INSTITUTE OF TECHNOLOGY filed Critical EUROPEAN INSTITUTE OF TECHNOLOGY
Publication of WO1994015280A2 publication Critical patent/WO1994015280A2/fr
Publication of WO1994015280A3 publication Critical patent/WO1994015280A3/fr
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F8/00—Arrangements for software engineering
    • G06F8/40—Transformation of program code
    • G06F8/41—Compilation
    • G06F8/44—Encoding
    • G06F8/445—Exploiting fine grain parallelism, i.e. parallelism at instruction level
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/30—Arrangements for executing machine instructions, e.g. instruction decode
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/44—Arrangements for executing specific programs
    • G06F9/448—Execution paradigms, e.g. implementations of programming paradigms
    • G06F9/4496—Unification in logic programming

Definitions

  • COMPUTER ARCHITECTURE FOR PARALLEL DATA TRANSFER IN DECLARATIVE COMPUTER LANGUAGES The present invention relates to apparatus and methods for computing and particularly for parallel manipulation of data in languages, such as declarative languages.
  • An important application of the invention is in parallel graph reduction machines.
  • Declarative languages are languages in which a program is written by defining functions and defining further functions in terms of those previously defined, examples include LISP and PROLOG.
  • Examples of abstract graph reduction machines include the G-machine, the ABC machine and the Spineless Tagless machine.
  • Such machines use functional languages such as LML, Haskell, Miranda and Clean (see Plasmeijer, van Eekelen, Nocker and Smetsers, "The Concurrent Clean System", University of Nijmegen, 1991; Jones and Salkild, "The spineless tagless G-machine", Proceedings of the FPLCA, pages 184 to 201, London, 1989; the Miranda System Manual, Canterbury, 1990; Report on the Programming Language HASKELL, version 2.0, Paul Hudak, 1992; and T. Johnsson "Compiling Lazy Functional Languages", Ph.D. thesis, Goteborg, 1987).
  • the invention is particularly applicable to the G-machine (see T. Johnsson, "Efficient Compilation of Lazy Evaluation", Sigplan Notices, 19(6): 58, 69, June 1984), and its derivatives.
  • Computation in a lazy graph reducer includes repeatedly re-writing a graph until a final result is obtained.
  • Two sections of memory are usually used for this purpose: one, known as the heap, contains nodes of the graph and the other, known as the stack, contains pointers and data.
  • re-writing a graph consisting of operations such as graph construction, unwinding and updating, data is frequently transferred between the stack and the heap and they are frequently accessed for this purpose.
  • Such access causes a bottleneck in most known implementations of graph reduction on existing processors since data transfer is controlled by the computer's CPU and passes by way of a single data bus. For much of the operating time one section of memory is awaiting data from another section.
  • the G-machines are all alike and synchronously execute code which is the same for each machine except that a "write” for the memory is handled by the machine for the appropriate memory section. No communication with other G-machines is required and thus writing can be carried out in parallel for graph construction.
  • a "read” for the heap is carried out in a similar way so that in the G-line machine data is moved from one of the memory banks via the global buses to all the G-machines.
  • All the G-machines carry out the complete program except that each manages its own section of memory in parallel with the others so that all machines are supplied with the data they need for carrying out the program.
  • each machine contains a replica of the two parts of the stack which are used: the value stack for values and the pointer stack for storing pointers.
  • Each machine also includes an ALU, a program counter and a control store. Since all machines operate the same program, care has to be taken to ensure that the replicas of the stacks and the program count remain identical in all machines.
  • the present invention is concerned with the movement of data to allow some of the operations to be carried out in parallel and in graph reduction these operations include graph construction (that is a process of writing the graph using the heap and the stack to postpone an evaluation), unwinding (that is a process of reading the graph to prepare for carrying out the evaluation, using the graph and the stack), updating the graph (that is a process of overwriting the graph with the result of an evaluation, using the heap and the stack), arithmetic and logical computation (using the ALU and may use stack and heap), and program control operations.
  • graph construction that is a process of writing the graph using the heap and the stack to postpone an evaluation
  • unwinding that is a process of reading the graph to prepare for carrying out the evaluation, using the graph and the stack
  • updating the graph that is a process of overwriting the graph with the result of an evaluation, using the heap and the stack
  • arithmetic and logical computation using the ALU and may use stack and heap
  • apparatus for computing comprising a first memory for storing data, a plurality of buses, a global processing unit for carrying out arithmetic and Boolean operations, with access to at least one of the buses and including program control means, a second memory for storing program code, a plurality of hinge means, each of which is arranged for data transfer from at least one of the buses, and to at least one of the buses, from a respective section of the first memory, means for transferring selected separate program code instructions for each hinge from sections of the second memory in each of successive intervals under the control of the program control means, each instruction relating to the said data transfer between one of the hinge means and one of the buses, and means for causing the hinge means to execute simultaneously the instructions received in each of the said intervals.
  • Each hinge means carries out operations required for data transfer and preferably some modifications of code and addresses required for graph operations such as construction, unwinding and updating.
  • Each hinge means may, for this reason, include a circuit for such modification which in its simplest form needs to be only an adder.
  • the main advantages of the invention include the provision of architecture for a practical machine, and this machine can handle both strict and lazy code in parallel operations.
  • Each memory module may be self-contained and the size of the memory can be easily scaled without an excessive hardware expansion.
  • part of the first memory is preferably used as the heap for storing nodes of a graph and part is used as the stack for storing data including pointers and values.
  • the stack itself may be divied into two parts, the pointer stack and the value stack.
  • the global processing unit and all the hinge means each have access to all buses.
  • the first and second memories may form part of the same address space.
  • the invention also includes methods of computing using a declarative language in which data is transferred in parallel between sections of memory under the control of separately instructed hinge means but the overall program is controlled from a single unit.
  • Figure 1 illustrates how graphs are held in apparatus according to the invention
  • FIG. 2 is a block diagram of apparatus according to the invention.
  • FIG. 3 is a block diagram of a heap hinge used in the apparatus of Figure 2
  • Figure 4 is a block diagram of a stack hinge used in the apparatus of Figure 2
  • FIG. 5 is a block diagram of a global processing unit of Figure 2
  • Figure 6 illustrates a stack section of memory
  • Figures 7 and 8 illustrate techniques of vertical and horizontal replication for mapping instructions to hinges
  • Figures 9 and 10 illustrate graph construction and show a stack section of memory before construction and a heap section and the stack section after graph construction.
  • Figure 11 illustrates an alternative interface between the global bus and the memory modules.
  • the node is represented by a header 10 having three fields and a vector 11 with four fields.
  • the first field of the header is a tag containing information about the node which is stored, in this example a vector apply node (VAP) with three arguments.
  • the second field is the heap address of the code required to carry out the function plus 3.
  • the third field of the header not used in this example and the fourth is a pointer to a vector which itself has four fields, the first describing the size of the vector and the other three specifying the arguments to be used by the plus 3 function. These arguments can either be values or pointers to further graph nodes.
  • a group of modules 12 includes the heap and comprises a number of modules indicated by rectangles such as those designated 13 and 14.
  • Each module includes a section of a first memory in a common address space and a hinge giving bidirectional access to a number of global buses 15 and a section of a second memory holding instructions.
  • the group 18 includes the stack formed by further sections of the first memory, one for each module.
  • each module includes a hinge for access to the buses 15 and a section 21 of the second memory.
  • a global processing unit 20 carries out those operations required by a program which do not involve data movement from heap to stack.
  • the global processing unit includes an arithmetic/logic unit (ALU) and a floating point unit (FPU) for carrying out the usual operations which occur in a conventional computer.
  • the global processing unit includes a program control unit (PCU) which controls the selection of code for each operation by means of a program count (PC).
  • the code itself is held in very long instruction words (VLIWs) held in the second memory, which is shown in three parts 21, 22 and 23.
  • VLIWs very long instruction words
  • Each module in the stack and heap has its own slot in the VLIW and another slot has instructions for the data path unit 20.
  • VLIWs very long instruction words
  • Each module in the stack and heap has its own slot in the VLIW and another slot has instructions for the data path unit 20.
  • the allocation of instruction memory slots to respective modules has to be carried out at "run time".
  • One way of achieving this allocation is indicated in Figure 2 and uses a stack switch 24 and a heap switch 25. These switches may be barrel shifters.
  • An alternative is
  • the memory sections of the heap and stack are usually, as mentioned, in a single address space.
  • the addresses of the memory sections of the modules are interleaved in that the least significant bits (LSBs) address the modules.
  • LSBs least significant bits
  • the modules of the heap are shown with addresses having LSBs 000, 001, 010, 011, 100, 101 and 111, respectively, so that a global address of 01101 refers to address 01 in module 101.
  • a similar addressing system is used for addressing the memory sections of the stack modules.
  • a cache may be placed between the stack hinge and stack memory, and/or between the heap hinge and heap memory. Such a cache is similar to a level 2 cache in the memory architecture of state of the art processors.
  • the architecture shown in Figure 2 allows transfer of data from the heap to the stack without involving the global processing unit.
  • Each stack and heap unit receives an individual instruction from a slot in the VLIW for this, and sometimes other, purposes.
  • MIMD multiple instruction multiple data
  • the buses are not configured or used for either data or address alone and any bus can be used for data or addresses.
  • a bus can operate as a conventional bus or can be regarded as a register.
  • Figure 2 shows eight modules in the heap but n practice any convenient number of modules may be used.
  • a heap of two modules is preferred but by the use of suitable code these two modules can in fact be used to form a heap with any even number of modules.
  • the number of fields in a subgraph node should equal the number of heap modules but in general this is not so. If a subgraph is small some modules have no field to write but if the subgraph is large then it must be wrapped around so that modules have to write more than one field. In wrapping round the module with the lowest LSB, for example 000, always receives the first field of a subgraph, so with eight modules and a subgraph of ten fields wrapping round extends to module 001. The next subgraph starts at module 000 and six modules are inactive. An alternative is "rotation" where the first field is allocated to the first available module, 010 in this example, and no modules are inactive. Replication or a barrel shifter can be used for this purpose as is explained below.
  • Input/output is by way of a port 8 and a connection 9 allows code to be loaded into the second memory 21, 22, 23.
  • FIG. 3 A block diagram of a heap module is shown in Figure 3 where the hinge in the form of additional circuits within a box 26 is shown.
  • these additional circuits allow the heap memory section access to the global buses and a slot 23' of the instruction memory 23 that they are collectively known as a hinge and the architecture is known as G-hinge architecture.
  • Instructions for graph reduction processes which can be carried out by the heap and stack modules are transferred for example, by the switch 25 or using replication, to a control register 27 under the control of the instruction unit in the global processing unit.
  • the control register 27 has control lines to other circuits in the hinge 26 but since these are of a conventional nature most of them will not be mentioned further. However data movement within the hinge and between the global buses 15, the heap memory (by way of a memory interface) and the control register 27 are controlled by some of these control lines which extend to selectors 28 and 30 controlling such movement.
  • a hinge can operate with one or more interfaces with the global buses.
  • An example of a hinge with two bus interfaces is shown in fig. 11.
  • a bus interface may be connected with only one of the global buses, but in the above example preferably with all of them.
  • a hinge has a separate bus interface with each of the global buses.
  • the value of each of the global buses is stored in data-in registers (100,101,102,103) in all hinges during each instruction cycle.
  • Selector 28 is used to select the global bus from which data must be read.
  • this can be realised by the selection of an appropriate data-in register. References to the selection of a global bus by selector 28 refer to the selection of the appropriate data-in register.
  • the selector 28 selects the global bus which holds the data which may be either input data or an address which is in turn to be used to address the heap memory section of the module.
  • the selector 30 selects the global bus to which data from the heap memory section in the module or from a register in the hinge has to be written to. In operation, the selector 28 selects one of the global buses for connection to either a maximum-heap register 31 or, when data is to be written to the heap memory section, an adder 32.
  • the maximum-heap register 31 contains the address of the top of that part of the address space allocated to the heap and it is loaded at load time or by a heap garbage collection routine.
  • a test comparator 34 compares the local heap pointer held by a register 35 with the contents of the register 31 and, if equal or the former is greater than the latter, generates an interrupt for the global processing unit which runs the heap garbage collection routine. However since only one of the heap modules needs to perform this task, the maximum-heap registers 31 of all heap modules except one are loaded to store a value which is too large so that only the said one module generates the interrupt.
  • An address selector 36 provides addresses to address the heap memory section of the module for read or write operations but the address provided may come from the local heap pointer register 35, one of the global buses 15 or the VLIW memory slot 23'.
  • the address may be constructed from the LSBs of the local heap pointer and the PC which is distributed from the GPU to all sections of the second memory, and for one form of replication (horizontal) the number of fields in a subgraph.
  • some modules only are enabled for a particular instruction and a comparator 38 (connected by a dashed line to indicate presence only in such replication) enables the VLIW slot 23' when the LSBs of the module are the same as the LSBs of the local heap pointer.
  • the local heap pointer register 35 contains the global heap pointer, that is the MSBs of the pointer, and the module address, that is the LSBs of the pointer.
  • Another adder 37 in operation, adds the number of words written in a current instruction cycle to the MSB part of the local heap pointer as will be understood from the example programs given later.
  • the adder 32 may also add an operand from the VLIW slot to the local heap pointer and then send the result to the heap memory section but in other operations, where no addition is required, zero is added before transfer to the memory section.
  • a stack hinge module may support one or two or more stacks but that module shown in Figure 4 supports two stacks: a pointer stack (Pstack) and a value stack (Vstack).
  • Two selectors 61 and 62 are provided and one, the selector 61, in operation, selects the global bus which is to hold data from the stack to be transferred to the heap memory and/or the GPU.
  • the other selector 62 selects the global bus via an appropriate data in register (100, 101, 102, 103) which is to send data to one of three destinations, a maximum Vstack register - ⁇ -
  • the registers 63 and 64 are loaded at load time with the locations of the end of the address space allocated to the value stack and the pointer stack, respectively.
  • a test comparator 66 compares the Vstack pointer and the Pstack pointer held by registers 67 and 68 with the contents of the registers 63 and 64, respectively, and initiates a garbage collection routine for the stack memory by way of an interrupt to the global processing unit if the former is equal to or greater than the latter.
  • An adder 69 increases or decreases the Pstack or Vstack pointer as required by VLIW instructions as will be apparent from the example programs described later, and another adder 70 uses the VLIW and the Pstack or Vstack pointer to compute addresses for the stack memory section.
  • another adder 70 uses the VLIW and the Pstack or Vstack pointer to compute addresses for the stack memory section.
  • the LSBs of the Pstack or Vstack pointer as appropriate are used to compute addresses in the VLIW slot 21' by concatenation of the LSBs with the MSBs of a VLIW instruction.
  • the global processing unit includes the program control unit 46 which provides the VLIW instruction words, the ALU and the FPU shown as one unit 47 but which operate in parallel (as indicated in Figure 2) from separate slots of the VLIW. Access to and from the global buses 15 is by way of a bus access unit 48 which is coupled to a register file 51 and the ALU/FPU 47 by three internal buses 52 one of which is also connected to the instruction unit 46. Two of these internal buses are source buses for the ALU/FPU and one is a destination bus.
  • the unit also contains a clock 49 which supplies clock pulses to the hinges as well as the circuits of the global processing unit and thus ensures simultaneous operation of the hinges.
  • the functionality of the global processing unit is different from that of conventional microprocessors since memory operations (load and store operations, and addressing modes) are distributed to the stack and heap hinges. Testing stack overflow and initiating garbage collection are also moved to the hinges. Also the instruction unit operates independently of the ALU.
  • the instruction unit includes a group of registers 53 comprising a swap register to hold the address of the next VLIW when an interrupt occurs, a stack-overflow register and a garbage-collection register, the latter two holding the addresses in the second memory of routines for dealing with stack overflow and garbage collection.
  • the interrupts which trigger these two routines are indicated by dashed arrows 54 and occur when the contents of the max stack and max heap registers, respectively, in the hinges are reached.
  • Registers 55 and 56 are used to hold selected values represented by one bit or a string of bits stored in a field of a graph for comparison with an operand in the code as mentioned in (d) of the explanation of selecting the next instruction given below.
  • the global processing unit may be implemented as a specially designed processor with two or three (as shown) parts running in parallel or two commercially available processors may be used where one is used for program control and the other for the ALU and FPU functions. Where one commercially available processor carries out program control a specially produced RISC processor which is much simpler than a conventional RISC processor can be designed.
  • Program control in a graph reducer differs from program control in a conventional processor where control is generally performed in parallel with other operations. In a graph reducer the control flow is determined by interpreting the type of a node. The next instruction is determined in five different ways:
  • an operand of a (conditional or unconditional) jump instruction in the code contains a new address and is moved to the program counter,
  • the contents of a field in the graph, or part of a field thereof contains the address, or part of the address of the next instruction as for example occurs when the address of a function is fetched from a function descriptor or if a node contains an address needed to perform an unwind operation,
  • a register for example one of the registers 53 or a bus.
  • a number of special instructions are required, each instruction, in operation, being held in a slot of the VLIW memory for transfer to the control register of a particular hinge or to the data path unit.
  • An example of a suitable set of instructions is now given.
  • SMSO #off bSrc Csize Store system bus to memory SMLO #off bDest Csize Load system bus from memory
  • bDest Destination system bus, that is a bus which is to hold data
  • bSrc Source system bus, that is the data in register which has been loaded with the contents of the bus which holds data
  • Csize Integer denoting the number of consecutive words allocated in the first memory during execution of a VLIW instruction.
  • the instructions which are used both in the heap and stack hinges, perform the actions to save and restore the contents of the local register (RSL and RSS), perform no operation (NOP), and add a value to the contents of the register (ADD).
  • Some other ALU operations may also be implemented, such as a compare test instruction (CMP).
  • Heap instructions can be divided into three groups, immediate operand, register offset and system bus instructions.
  • the IMSx instruction writes the immediate operand to the specified memory location.
  • the memory base address is contained in the local register 35 or the bSrc system bus.
  • the RMS instruction writes the result of the addition of the contents of the local register and the immediate operand to the specified memory location.
  • the memory base address is contained in the local register 35.
  • the SMSx instruction writes the contents of the local system bus to the specified memory location.
  • the bSrc field is used to specify the system bus data that will be stored in memory.
  • the memory base address is contained in the local register or bDest system bus.
  • the SML instruction reads data from the specified memory location and loads it into the destination system bus.
  • the memory base address is contained in bSrc system bus.
  • the global stack address is always computed relative to the top of the stack.
  • the SMSO instruction writes the contents of the specified system bus to the specified memory location.
  • the bSrc field is used to specify the system bus data that will be stored in memory.
  • the memory base address is the result of the addition of the local register with the immediate offset.
  • the SMLO instruction reads data from the specified memory location and loads it into the destination system bus.
  • the memory base address is the result of the addition of the local register with the immediate offset.
  • mapping the stack and heap instruction slots on the stack and heap modules is carried out at run time because it is unknown at compile time, for example when "rotation" is used, which module will be addressed by the stack or heap pointer when a certain VLIW instruction is executed.
  • Either the stack switch 24,25 of Figure 2 or a technique of code replication can be used.
  • FIG. 6 A typical situation is shown in Figure 6 where at run time part of an address space 18' containing the memory sections of four stack modules illustrated as columns is shown.
  • the memory space 18' has addresses which begin at the top right-hand corner and increase from right to left. Six locations are shown as being occupied by the stack, these address locations being indicated by the numbers 0000 to 0101 which also indicate the offset of any occupied memory location from the top of the memory stack.
  • the global address of the stack pointer indicates the next vacant location in the address space and in the example shown has the value 0110.
  • the most significant bits (MSBs) 01 provide a common address to all stack memory section modules while the LSBs 10 indicate the module in which the next vacant location exists, this location being indicated by shading.
  • FIG. 7 An example of the former is given with reference to Figure 7 where four additional memory sections 40 to 43, one for each of four stack modules, are shown, each section being part of the second memory and effectively interposed between the VLIW memory slot 23' and the control register 27 of Figure 3, that is in the position of the stack switch 24 in Figure 2.
  • Each additional memory section contains four instruction words 0, 1, 2 and 3.
  • each module has available each of four possible instruction slots from the VLIW covering each of the four mapping arrangements which may be required, and it is necessary to select the correct instruction slot for each module.
  • the VLIW code is written for the situation in which the stack pointer points to an address location in the first module (00) and in Figure 7, instruction slots 0 to 3 are shifted one place to the left with increase in module designation.
  • the modules are allocated to groups in which the number of modules equals the number of fields in a node, and the control registers 27 of each group receive respective instruction slots relating the node, so that the groups of modules receive the same instruction slots. For example if a subgraph having a single node with two fields (#itag and value #47) is to be written to the heap, the instructions for this node (ISMB #itag and ISMB #47) corresponding to slot 0 and slot 1 are written to the control registers 27 in the way shown in Figure 8 where the control registers 27 of eight heap modules 000 to 111 are shown. Groups of two modules receive the two instructions, and these instructions are repeated in four groups.
  • the two heap modules which are enabled to perform the two instructions stored depend on the LSBs of the heap pointer which in this situation indicates the next free location. For this to occur the heap instructions are stored in the second memory in the replicated form.
  • the heap part of a VLIW would be as shown in Figure 8 with four identical words, but for a heap instruction of four words there would be two identical words, while for eight words there would be a single word.
  • the PC is used to select VLIW instructions which are transferred to the groups of control registers having a size determined by Csize (the number of words in part of a subgraph) and then the modules whose LSBs match those of the heap pointer are enabled. Thus "rotation" is again implemented. Since empty locations are not allowed in the stack, only vertical replication can be used for the stack. Both vertical and horizontal replication can be used for the heap.
  • the example program is as follows:- com ent
  • heap 0 RSL 0 move Lheapptr to bus 0
  • heap 0 write VAP3 in heap 0 add 8 to hp heap 1 write plus3 in heap 1, add 8 to hp heap add 8 to heap 2 heap write Lheapptr +4 in heap, add 8 to hp heap write 3 in heap, add 8 to hp heap move bus 3 to heap, add 8 to hp heap move bus 3 to heap, add 8 to hp heap move bus 1 to heap, add 8 to hp
  • a $ sign denotes a new VLIW instruction and different functional units in a hinge are, in general, activated by the same instruction slot. Operations that are executed by the same instruction slot are written on the same line.
  • the two columns following the $ signs indicate the module carrying out the instruction by specifying its number and whether it is in the stack or heap.
  • the next column is an instruction and it is followed by two columns giving operands and a further column providing an argument.
  • the argument in this further column is used in the parallel operations given in the last two columns to increment pointers and which are carried out at the same time as the operations to the left and in the same hinge.
  • the first three operations, SMLO, load buses 3, 2 and 1 from stack locations offset from the stack pointer by offsets #1, #2 and #3, respectively.
  • the next group of parallel operations includes an SMSO operation for stack hinge 0 which writes the contents of bus 0 (that is the local heap pointer) to a stack location with zero offset from the stack pointer as held by the local stack pointer register equivalent to the register 35 of a heap module.
  • the heap pointer hp is now on the stack in the position shown in Figure 10, assuming the first, second and third locations of the stack section of memory are occupied.
  • the seven heap operations for modules 0 to 7 are carried out in parallel, the first two write the function tag and the pointer to the descriptor of the function "plus3", to addresses indicated by the local heap pointer as held by the register 34, while since the third field is empty heap module 2 does not carry out an operation (NOP).
  • Heap module 3 carries out the RMS operation of adding the contents of the register 34 containing a heap pointer to the value #4 to give a pointer to the vector, the result being stored as indicated by the local heap pointer.
  • Heap module 4 writes the size of the, #3, to the location pointed by the heap pointer and heap modules 5, 6 and 7 write the contents of the buses 3, 2 and 1 also to locations indicated by their local heap pointers.
  • each of these last nine parallel operations is carried out in conjunction with an addition operation.
  • stack module 0 the stack pointer is increased by 1 and for heap modules 0 to 7 the contents of the local heap registers 34, that is the local heap pointers, are incremented by 8, this being the number of fields in the node (Csize).
  • the stack pointer points to the first field in the subgraph as held by the heap, and in a first stack operation, the pointer is stored on bus 0.
  • the program count in the register 45 (see Figure 5) is saved in a register 0 of the registers 53. Instructions for these two operations appear under $eval (being the address of the code to execute eval) in the above program.
  • the GPU moves the second field "plus3" from bus 1 to a register 1 of the registers 53.
  • each G-line machine retrieves the data required and performs the calculation, these operations occurring in sequence.
  • some data fetch operations can, for example be carried out in parallel, and then some preliminary calculations can be performed while more data is retrieved in parallel, and so on.
  • parallelizing strict computations is possible on the G-hinge machine but not on the G-line machine.
  • the architecture of the hinge can be implemented by pipelining the execution of instructions. By using techniques which are applied in the processor architecture of modern RISC processors, vertical instruction parallelism is increased. Reading from a system bus, computing the new value of the heap pointer or stack pointer or fetching the next instruction can all be executed in the time that the hinge is waiting for a memory access to finish.
  • the invention can also be put into effect in many different ways from those specifically described above, for example different machines use different stack systems.
  • the ABC machine of Koopman uses three different stacks and in the implementation of Clean these are mapped onto two hardware stacks. This is also true of the Spineless Tagless Machine and the Nu-G-machine uses no separate hardware stack at all but allocates the stack in the heap.
  • the G-machine a value stack and a pointer stack are used, one growing from the bottom of the address space and one downward from the top of the address space. Each is separately handled in the way described above but two local pointer registers, equivalent to the register 35 of heap modules are required.
  • the invention is not limited to machines for carrying out graph reduction since it is believed that the invention can be used for many machines employing a declarative language.
  • any such machine definitions depend on other definitions and for this reason there is a great deal of transfer from one portion of memory to another, some small amount of computation, mainly of addresses, being involved.
  • such movement can be handled by memory modules, containing a few additional components forming hinges, without involving the CPU.
  • the G-machine is related to the SECD abstract machine which is designed as, and often used as, an intermediate between LISP and a target machine (see P.J. Landin, "The mechanical evaluation of expressions", The Computer Journal, Vol. 6, No. 4, pp 308-320, Jan. 1964). Also data structures in the SECD machine can be mapped on the functional units of the G-hinge. Thus it is apparent that the invention can be used in relation to LISP. Since PROLOG uses memory heavily and memory is implemented as stack and heap, and also because PROLOG is often used for symbolic, non-numeric, computations, as are function-based languages, with consequent irregular memory-access patterns, it is believed that the invention is also applicable to this language.

Landscapes

  • Engineering & Computer Science (AREA)
  • Software Systems (AREA)
  • Theoretical Computer Science (AREA)
  • General Engineering & Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Executing Machine-Instructions (AREA)

Abstract

Les calculs effectués par des machines de réduction de graphes réalisant une réduction de graphe paresseuse impliquent de ré-écrire un tel graphe de façon répétitive jusqu'à l'obtention d'un résultat final. A cette fin, une mémoire est divisée en sections d'entreposage et de pile faisant l'objet d'accès fréquents entraînant un embouteillage car le transfert de données est commandé par une unité centrale de traitement (CPU) et transite par un seul bus de données. On résout ce problème en utilisant plusieurs modules (13, 14, 16, 17) comprenant chacun une section de mémoire d'entreposage ou de mémoire de pile, une unité arithmétique/logique (ALU) et une charnière (dispositif de commutation) destinée à coupler la section de mémoire à un réseau de bus (15) du système ou à une mémoire d'instruction à très longs mots d'instruction (VLIW) (21, 22, 23). Le transfert de données entre l'entreposage et la pile peut alors s'effectuer en parallèle sans recourir à un circuit de traitement global (20), lequel effectue toutes les opérations de calcul conventionnelles qui n'impliquent aucun transfert de données et commande aussi le fonctionnement de l'ensemble du programme stocké dans la mémoire VLIW. De façon générale, cette architecture convient spécialement au parallélisme concernant le niveau des instructions où beaucoup de ces dernières concernent des opérations liées à la mémoire.
PCT/EP1993/003636 1992-12-18 1993-12-20 Architecture informatique destinee au transfert de donnees parallele dans des langages informatiques declaratifs Ceased WO1994015280A2 (fr)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
EP92311586 1992-12-18
EP92311586.9 1992-12-18

Publications (2)

Publication Number Publication Date
WO1994015280A2 true WO1994015280A2 (fr) 1994-07-07
WO1994015280A3 WO1994015280A3 (fr) 1994-09-01

Family

ID=8211582

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/EP1993/003636 Ceased WO1994015280A2 (fr) 1992-12-18 1993-12-20 Architecture informatique destinee au transfert de donnees parallele dans des langages informatiques declaratifs

Country Status (1)

Country Link
WO (1) WO1994015280A2 (fr)

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2000004484A3 (fr) * 1998-07-17 2000-07-06 Intergraph Corp Processeur graphique a mot instruction long
US6542989B2 (en) * 1999-06-15 2003-04-01 Koninklijke Philips Electronics N.V. Single instruction having op code and stack control field

Family Cites Families (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
NL9100598A (nl) * 1991-04-05 1992-11-02 Henk Corporaal Move: een flexibele en uitbreidbare architectuur voor het ontwerpen van processoren.

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2000004484A3 (fr) * 1998-07-17 2000-07-06 Intergraph Corp Processeur graphique a mot instruction long
US6542989B2 (en) * 1999-06-15 2003-04-01 Koninklijke Philips Electronics N.V. Single instruction having op code and stack control field

Also Published As

Publication number Publication date
WO1994015280A3 (fr) 1994-09-01

Similar Documents

Publication Publication Date Title
US8239660B2 (en) Processor with automatic scheduling of operations
US7610475B2 (en) Programmable logic configuration for instruction extensions
US5872985A (en) Switching multi-context processor and method overcoming pipeline vacancies
US8161266B2 (en) Replicating opcode to other lanes and modifying argument register to others in vector portion for parallel operation
US6298434B1 (en) Data processing device for processing virtual machine instructions
JP3531166B2 (ja) レジスタ・リネーミングのシステム及び方法
US8935515B2 (en) Method and apparatus for vector execution on a scalar machine
EP0365188B1 (fr) Méthode et dispositif pour code de condition dans un processeur central
US5367650A (en) Method and apparauts for parallel exchange operation in a pipelined processor
US5619680A (en) Methods and apparatus for concurrent execution of serial computing instructions using combinatorial architecture for program partitioning
RU2427895C2 (ru) Оптимизированная для потоков многопроцессорная архитектура
EP0476722A2 (fr) Système de traitement de données
US6338134B1 (en) Method and system in a superscalar data processing system for the efficient processing of an instruction by moving only pointers to data
US6292845B1 (en) Processing unit having independent execution units for parallel execution of instructions of different category with instructions having specific bits indicating instruction size and category respectively
US11822541B2 (en) Techniques for storing sub-alignment data when accelerating Smith-Waterman sequence alignments
JP2001501001A (ja) データ処理システムにおける入力オペランド制御
US5752271A (en) Method and apparatus for using double precision addressable registers for single precision data
WO1994015280A2 (fr) Architecture informatique destinee au transfert de donnees parallele dans des langages informatiques declaratifs
US5293499A (en) Apparatus for executing a RISC store and RI instruction pair in two clock cycles
EP1035471A1 (fr) Systeme informatique
US5396640A (en) Boosting method and apparatus in a parallel computer
US12572457B2 (en) Processor suitable for multi-segment accessing memory and operation method thereof
JP2729795B2 (ja) 並列計算機及びその制御方法
Maurer Mapping the Data Flow Model of Computation into an Enhanced Von Neumann Processor.
JPH0744401A (ja) 論理集積回路およびそのデータ処理システム

Legal Events

Date Code Title Description
AK Designated states

Kind code of ref document: A2

Designated state(s): JP US

Kind code of ref document: A1

Designated state(s): JP US

AL Designated countries for regional patents

Kind code of ref document: A1

Designated state(s): AT BE CH DE DK ES FR GB GR IE IT LU MC NL PT SE

Kind code of ref document: A2

Designated state(s): AT BE CH DE DK ES FR GB GR IE IT LU MC NL PT SE

CFP Corrected version of a pamphlet front page
CR1 Correction of entry in section i

Free format text: PAT.BUL.15/94 UNDER PUBLISHED REPLACE "A1" BY "A2"

AK Designated states

Kind code of ref document: A3

Designated state(s): JP US

AL Designated countries for regional patents

Kind code of ref document: A3

Designated state(s): AT BE CH DE DK ES FR GB GR IE IT LU MC NL PT SE

DFPE Request for preliminary examination filed prior to expiration of 19th month from priority date (pct application filed before 20040101)
121 Ep: the epo has been informed by wipo that ep was designated in this application
122 Ep: pct application non-entry in european phase