公开(公告)号：US07363459B2

公开(公告)日：2008-04-22

申请号：US10284844

申请日：2002-10-31

申请人： Robert S. Schreiber ,  Alain Darte

发明人： Robert S. Schreiber ,  Alain Darte

IPC分类号： G06F12/00

CPC分类号： G06F8/4442

摘要： A method of storing data includes the steps of storing data comprising the steps of identifying respective lifetimes of each member of an indexed collection of data elements, each of the data elements referenceable in a data index space representing a set of valid data element indices; identifying a set of pairs of the data elements having overlapping lifetimes; and generating a mapping from the data index space to an address offset space based on the set of pairs of the data elements having the overlapping lifetimes.

摘要翻译： 存储数据的方法包括存储数据的步骤，包括以下步骤：识别索引的数据元素集合的每个成员的相应寿命，每个数据元素可在表示一组有效数据元素索引的数据索引空间中引用; 识别具有重叠生命周期的一组数据元素对; 以及基于具有重叠寿命的数据元素对的集合，生成从数据索引空间到地址偏移空间的映射。

公开(公告)号：US06438747B1

公开(公告)日：2002-08-20

申请号：US09378393

申请日：1999-08-20

申请人： Robert S. Schreiber ,  Bantwal Ramakrishna Rau ,  Alain Darte

发明人： Robert S. Schreiber ,  Bantwal Ramakrishna Rau ,  Alain Darte

IPC分类号： G06F945

CPC分类号： G06F8/452

摘要： A parallel compiler maps iterations of a nested loop to processor elements in a parallel array and schedules a start time for each iteration such that the processor elements are fully utilized without being overloaded. The compiler employs an efficient and direct method for generating a set of iteration schedules that satisfy the following constraints: no more than one iteration is in initiated per processor element in a specified initiation interval, and a new iteration begins on each processor element nearly every initiation interval. Since the iteration scheduling method efficiently generates a set of schedules, the compiler can select an iteration schedule that is optimized based on other criteria, such as memory bandwidth, local memory size of each processor element, estimated hardware cost of each processor element, etc. The iteration scheduling method is useful for compilers where the underlying architecture is fixed, as well as for an automated processor array synthesis system where the nested loop is converted into a set of parallel processes for synthesis into a parallel processor array.

摘要翻译： 并行编译器将嵌套循环的迭代映射到并行数组中的处理器元素，并为每次迭代调度开始时间，以使处理器元素得到充分利用而不会过载。 编译器使用一种有效和直接的方法来生成一组满足以下约束的迭代计划：在指定的启动间隔内每个处理器元素不超过一次迭代，并且每个处理器元素上几乎每个启动都会开始一个新的迭代 间隔。 由于迭代调度方法有效地生成一组调度，编译器可以选择基于其他标准优化的迭代调度，例如存储器带宽，每个处理器元件的本地存储器大小，每个处理器元件的估计硬件成本等。 迭代调度方法对于底层架构是固定的编译器以及自动化处理器阵列合成系统是有用的，其中嵌套循环被转换成一组用于合并到并行处理器阵列中的并行进程。

公开(公告)号：US06374403B1

公开(公告)日：2002-04-16

申请号：US09378397

申请日：1999-08-20

申请人： Alain Darte ,  Robert S. Schreiber

发明人： Alain Darte ,  Robert S. Schreiber

IPC分类号： G06F945

CPC分类号： G06F8/45

摘要： A parallel compiler exploits temporal recursion to reduce the cost of control code generated in transforming a sequential nested loop program into a set of parallel processes mapped to an array of processors. A parallel compiler process transforms a nested loop program into a set of single loops, where each single loop is assigned to execute on a processor element in a parallel processor array. The parallel compiler obtains a mapping of iterations of the nested loop to processor elements in the array and a schedule of start times for initiating execution of the iterations on corresponding processor elements in the array. Based on this mapping and iteration schedule, the parallel compiler generates code to compute iteration coordinates on a processor element for an iteration of the single loop from iteration coordinates computed on the same processor element for a previous iteration of the single loop. The parallel compiler uses this method to generate code to compute loop indices, memory addresses, and tests of loop bounds efficiently based on values from a previous iteration.

摘要翻译： 并行编译器利用时间递归来降低将顺序嵌套循环程序转换成映射到处理器阵列的一组并行进程中生成的控制代码的成本。 并行编译器过程将嵌套循环程序转换为单个循环，其中每个单个循环被分配为在并行处理器阵列中的处理器元件上执行。 并行编译器获得嵌套循环迭代到数组中的处理器元素的映射，以及用于启动数组中相应处理器元素上的迭代执行的开始时间表。 基于该映射和迭代计划，并行编译器生成代码，用于计算处理器元件上的迭代坐标，用于从单个循环的先前迭代在相同处理器单元上计算的迭代坐标中迭代单个循环。 并行编译器使用此方法生成代码，以根据先前迭代的值有效地计算循环索引，内存地址和循环边界的测试。