Tilera Corporation

Vineet Soni

Richard Schooler

Anant Agarwal

Robert A Gottlieb

Walter Lee

Mathew Hostetter

A system comprises a plurality of computation units interconnected by an interconnection network. A method for configuring the system comprises forming subsets of instructions corresponding to different portions of a program, the subsets of instructions being related according to a control flow graph; for each of a first subset of branches in the control flow graph, scheduling a value of an associated branch condition to be broadcast to multiple computation units; for each of a second subset of branches in the control flow graph, representing each instruction dependent on an associated branch condition as a predicated instruction that includes a predicate for computing the associated branch condition; assigning each subset of instructions to one of the computation units for execution on the assigned computation unit; and converting at least some of the predicated instructions in a subset of instructions assigned to a given computation unit into unpredicated instructions that depend on a branch local to the given computation unit.

Compiling code for parallel processing architectures based on control flow

The present invention relates to a method, system, and computer program product for performing a computer program analysis. The computer program includes a plurality of instructions. The method performs a static analysis of the computer program to compute the states of a stack pointer (SP), a frame pointer (FP), and a link register (LR) at one or more instructions of the program. The static analysis is preferably performed at compile time. Further, the method computes the states of the SP, the FP, and the LR at the instructions as determined by a dynamic analysis, wherein the dynamic analysis is preferably modeled (performed) during the static analysis. Furthermore, the states determined by the static analysis and the dynamic analysis are compared. If a discrepancy is found between the two states, metadata (information operators) is inserted into the program.

Method and system for stack back-tracing in computer programs

A system comprises a plurality of computation units interconnected by an interconnection network. A method for configuring the system comprises receiving subsets of instructions corresponding to different portions of a program, each subset assigned to one of the computation units; scheduling instructions in a given subset for execution on the assigned computation unit, including scheduling communication instructions that send to or receive from a different computation unit over the interconnection network; allocating registers in a given computation unit for storing values accessed by instructions in a subset assigned to the given computation unit; and scheduling instructions after allocating registers to account for spills of values stored in allocated register to memory, preserving the order of communication instructions scheduled before allocating registers.

Communication scheduling for parallel processing architectures

A system comprises a plurality of computation units interconnected by an interconnection network. A method for configuring the system comprises receiving an initial partitioning of instructions into initial subsets corresponding to different portions of a program; forming a refined partitioning of the instructions into refined subsets each including one or more of the initial subsets, including determining whether to combine a first subset and a second subset to form a third subset according to a comparison of a communication cost between the first subset and second subset and a load cost of the third subset that is based at least in part on a number of instructions issued per cycle by a computation unit; and assigning each refined subset of instructions to one of the computation units for execution on the assigned computation unit.

Distributing parallelism for parallel processing architectures

A system comprises a plurality of computation units interconnected by an interconnection network. A method for configuring the system comprises forming subsets of instructions corresponding to different portions of a program, the subsets of instructions being related according to a control flow graph; forming one or more memory analysis regions that include one or more of the subsets of instructions, where each subset of instructions is included in a single memory analysis region; analyzing each memory analysis region to partition memory objects and instructions that access the memory objects into equivalence classes such that instructions within an equivalence class only access objects in the same equivalence class; and assigning memory access instructions a given equivalence class to one of the computation units for execution on the assigned computation unit.

Growing community of inventors

Union City, CA, United States of America

Vineet Soni