公开(公告)号：US06434566B1

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

申请号：US09203066

申请日：1998-12-01

申请人： Paolo Ferragina ,  Shanmugavelayut Muthukrishnan

发明人： Paolo Ferragina ,  Shanmugavelayut Muthukrishnan

IPC分类号： G06F1700

CPC分类号： G06F9/449 ,  Y10S707/99943 ,  Y10S707/99944

摘要： A method and system for efficiently resolving the multi-method dispatching problem provided. The dispatching problem is reduced to geometric problems on multi-dimensional grids and new data structures are provided for the resulting geometric problems. In particular, methods having the same name are mapped to a set of rectangles based on a pair of numbers associated with each argument. The pair of numbers is an interval identifying the position of the argument in a class hierarchy tree. The interval is found by computing an Euler Tour of the class hierarchy tree. For a given method invocation in an object-oriented program, the method invocation is mapped to a point based on one of the numbers in the interval associated with each argument in the invocation. The problem of finding the most specific method for the method invocation is thus transformed into the so-called point enclosure problem in geometry, in which the smallest rectangle is found which encloses a given point. To help find efficient solutions to the point enclosure problem, the set of rectangles is broken into a number of subsets having certain geometric properties and stored in efficient data structures. Queries are performed on the various data structures to find the smallest or minimal rectangle, if any, in the various subsets. The result is either the identification of the minimal rectangle overall, or of an ambiguity requiring resolution by the programmer.

摘要翻译： 一种有效解决提供的多方式调度问题的方法和系统。 调度问题减少到多维网格上的几何问题，为所得到的几何问题提供了新的数据结构。 特别地，具有相同名称的方法基于与每个参数相关联的一对数字映射到一组矩形。 一对数字是在类层次树中标识参数位置的间隔。 间隔是通过计算类层次树的欧拉之旅找到的。 对于面向对象程序中的给定方法调用，根据调用中每个参数的间隔中的一个数字，将方法调用映射到一个点。 因此，找到方法调用的最具体方法的问题被转换成几何中所谓的点围绕问题，其中找到包围给定点的最小矩形。 为了帮助找到有效的解决方案来解决问题，该组矩形被分解成具有某些几何属性并存储在有效数据结构中的多个子集。 对各种数据结构执行查询，以查找各种子集中的最小或最小矩形（如果有的话）。 结果是总体识别最小矩形，或程序员需要解析的歧义。

公开(公告)号：US06591287B1

公开(公告)日：2003-07-08

申请号：US09391470

申请日：1999-09-08

申请人： Sachin S. More ,  Shanmugavelayut Muthukrishnan ,  Elizabeth Shriver

发明人： Sachin S. More ,  Shanmugavelayut Muthukrishnan ,  Elizabeth Shriver

IPC分类号： G06F900

CPC分类号： G06F9/4881 ,  G06F15/161

摘要： A method and apparatus for scheduling jobs having a staging time and a processing time are described. In one method, the jobs are divided into subsets based on a predetermined criteria such as depending on whether the staging time is longer than the processing time. In this method, the jobs in each subset are ordered independently. The jobs are then scheduled by alternating between the ordered subsets. In a second method, the jobs are again divided into subsets based on a predetermined criteria such as depending on whether the staging time is longer than the processing time. The jobs in each subset are ordered independently. The jobs in one subset are then simply appended to the other subset. In a third method, the jobs are ordered according to a predetermined criterion into a list and are executed by alternating between both ends of the list. The invention is also applicable to scheduling jobs having a destaging time. In this case, the staging time is set equal to the staging time plus the processing time and the processing time is set equal to the processing time plus the destaging time. The jobs are then scheduled according to the second method discussed above.

摘要翻译： 描述用于调度具有分段时间和处理时间的作业的方法和装置。 在一种方法中，基于预定标准将作业划分为子集，例如取决于登台时间是否长于处理时间。 在这种方法中，每个子集中的作业都是独立排序的。 然后通过在有序子集之间交替排列作业。 在第二种方法中，根据预定标准（例如取决于分段时间是否长于处理时间）将作业再次划分为子集。 每个子集中的作业都是独立的。 然后将一个子集中的作业简单地附加到另一个子集中。 在第三种方法中，将作业根据预定标准排列成列表，并且通过在列表的两端之间交替来执行。 本发明也适用于调度具有降级时间的作业。 在这种情况下，将分段时间设置为等于分段时间加上处理时间，并且将处理时间设置为等于处理时间加上降级时间。 然后根据上述第二种方法安排作业。

公开(公告)号：US06502062B1

公开(公告)日：2002-12-31

申请号：US09337865

申请日：1999-06-21

申请人： Swarup Acharya ,  Shanmugavelayut Muthukrishnan ,  Ganapathy Sundaram

发明人： Swarup Acharya ,  Shanmugavelayut Muthukrishnan ,  Ganapathy Sundaram

IPC分类号： G06F1300

CPC分类号： G06F9/505

摘要： In accordance with one embodiment, a method for scheduling the servicing of job requests in a point-to-point communication system having a central server providing job requests to a plurality of local channel servers. In a first step, the method receives a new job request at a central server. A performance of each local channel server is measured, and the job request is dispatched to one of the local channel servers for servicing thereby dependent upon the performance of each of the local channel servers. In one embodiment, the job request is dispatched to the local channel servers having the lowest current average flow time. In another embodiment, the job request is dispatched to the local channel server having the lowest current maximum stretch value, wherein a stretch value is a ratio equal to an amount of time required to service a job request while also serving other uncompleted job requests, divided by an amount of time required to service said job request if no other job requests were required to be serviced.

摘要翻译： 根据一个实施例，一种用于在具有向多个本地信道服务器提供工作请求的中央服务器的点对点通信系统中调度对作业请求的服务的方法。 在第一步中，该方法在中央服务器处接收新的作业请求。 测量每个本地信道服务器的性能，并且将作业请求分派到本地信道服务器之一进行服务，从而取决于每个本地信道服务器的性能。 在一个实施例中，作业请求被调度到具有最低当前平均流动时间的本地信道服务器。 在另一个实施例中，将作业请求调度到具有最低当前最大拉伸值的本地通道服务器，其中拉伸值是等于服务作业请求所需的时间量的比率，同时还提供其他未完成的作业请求 如果不需要其他工作请求进行维修，则需要服务所述工作请求所需的时间。

公开(公告)号：US08156156B2

公开(公告)日：2012-04-10

申请号：US11783288

申请日：2007-04-06

申请人： Paolo Ferragina ,  Fabrizion Luccio ,  Giovanni Manzini ,  Shanmugavelayut Muthukrishnan

发明人： Paolo Ferragina ,  Fabrizion Luccio ,  Giovanni Manzini ,  Shanmugavelayut Muthukrishnan

IPC分类号： G06F7/00 ,  G06F17/30

CPC分类号： G06F17/30961

摘要： A method of structuring and compressing labeled trees of arbitrary degree and shape for optimal succinctness, the method including a transform for compressing and indexing tree shaped data, using path sorting and grouping to linearize labeled tree shaped data into two coordinated arrays, one capturing the structure of the tree and the other capturing the labels of the tree. Additional navigational operations and basic searching may be performed on the transformed data.

摘要翻译： 一种构造和压缩任意程度和形状的标准树以实现最佳简洁度的方法，该方法包括用于压缩和索引树形数据的变换，使用路径排序和分组将标记的树状数据线性化成两个协调的阵列，一个捕获结构 的树，另一个捕获树的标签。 可以对转换的数据执行附加的导航操作和基本搜索。

公开(公告)号：US06571391B1

公开(公告)日：2003-05-27

申请号：US09174228

申请日：1998-10-16

申请人： Swarup Acharya ,  Shanmugavelayut Muthukrishnan

发明人： Swarup Acharya ,  Shanmugavelayut Muthukrishnan

IPC分类号： H04N7173

CPC分类号： G06F9/4887

摘要： In accordance with one embodiment of the invention, a broadcast server system computes a feasible stretch value for use in scheduling job requests. A stretch value provides an indication of the delay experienced by each job request to complete, when the broadcast server processes many jobs concurrently. A processing time is calculated for each job request based on, the size of the job request and the bandwidth of the server downlink. Thereafter, a stretch value is proposed. The server system computes a deadline for each job to be the arrival time of the job request plus the product of the processing time and the proposed stretch value. Thereafter, each job request is scheduled, based on an “earliest deadline first” arrangement, wherein the job request that has the earliest deadline is scheduled first, the job request having the next earliest deadline is scheduled second, etc. The proposed stretch value is deemed feasible if each pending job request can be completed prior to its deadline. If the proposed stretch value is deemed not feasible, it is adjusted iteratively until a feasible stretch value is found. The feasible stretch value is then utilized to schedule the job requests to be broadcast by the system. When the broadcast of a job request is completed, all job requests for the same data item, which arrived prior to the start of the broadcast, are eliminated from the pending job requests.

摘要翻译： 根据本发明的一个实施例，广播服务器系统计算用于调度作业请求的可行拉伸值。 当广播服务器同时处理许多作业时，延伸值提供每个作业请求完成所经历的延迟的指示。 基于作业请求的大小和服务器下行链路的带宽，为每个作业请求计算处理时间。 此后，提出了拉伸值。 服务器系统将每个作业的期限计算为作业请求的到达时间加上处理时间和所提出的拉伸值的乘积。 此后，基于“最早期限”排列来安排每个作业请求，其中首先调度具有最早期限的作业请求，具有下一个最后期限的作业请求被调度为第二等等。所提出的拉伸值是 如果每个待处理的工作请求可以在其截止日期之前完成，则认为可行。 如果提出的拉伸值被认为不可行，则迭代地进行调整，直到找到可行的拉伸值。 然后使用可行的拉伸值来调度由系统广播的作业请求。 当完成作业请求的广播时，在广播开始之前到达的相同数据项的所有作业请求从待处理的作业请求中消除。

公开(公告)号：US07058946B2

公开(公告)日：2006-06-06

申请号：US10659757

申请日：2003-09-10

申请人： Swarup Acharya ,  Shanmugavelayut Muthukrishnan ,  Ganapathy Sundaram

发明人： Swarup Acharya ,  Shanmugavelayut Muthukrishnan ,  Ganapathy Sundaram

IPC分类号： G06F9/46 ,  H04Q7/00 ,  H04Q7/28

CPC分类号： G06F9/4881 ,  H04L67/1002 ,  H04L69/14

摘要： In accordance with one embodiment of the invention, a central server system computes a feasible stretch value for use in scheduling the servicing of job requests by a plurality of communication channels. A stretch value provides an indication of the delay experienced by each job request to complete, when the central server processes many jobs concurrently. A processing time is calculated for each job request based on the size of the job request and the bandwidth of the channel. Thereafter, a stretch value is proposed. The server system computes a deadline for each job to be the arrival time of the job request plus the product of the processing time and the proposed stretch value. Thereafter, each job request is scheduled, based on an “earliest deadline first” arrangement. According to the EDF methodology, the central server schedules for service, via k local channel servers, the job requests, such that the k job requests which have the earliest deadlines are serviced first by the k local channel servers and the remaining job requests are subsequently serviced as the local channel servers become available. The proposed stretch value is deemed feasible if each pending job request can be completed prior to its deadline. If the proposed stretch value is deemed not feasible, it is adjusted iteratively until a feasible stretch value is found. The feasible stretch value is then utilized to schedule the job requests to be serviced by the channels.

摘要翻译： 根据本发明的一个实施例，中央服务器系统计算用于通过多个通信信道调度对作业请求的服务的可行拉伸值。 当中央服务器同时处理许多作业时，拉伸值提供每个作业请求完成的延迟的指示。 基于作业请求的大小和频道的带宽，为每个作业请求计算处理时间。 此后，提出了拉伸值。 服务器系统将每个作业的期限计算为作业请求的到达时间加上处理时间和所提出的拉伸值的乘积。 此后，根据“最早的期限第一”安排安排每个工作请求。 根据EDF方法，中央服务器通过k个本地信道服务器对作业请求进行服务调度，使得k个本地信道服务器首先提供具有最早期限的k个作业请求以及其余的作业请求 随着本地频道服务器可用， 如果每个待处理的作业请求可以在其截止日期之前完成，则所提出的拉伸值被认为是可行的。 如果提出的拉伸值被认为不可行，则迭代地进行调整，直到找到可行的拉伸值。 然后使用可行的拉伸值来调度由通道服务的作业请求。

公开(公告)号：US06324540B1

公开(公告)日：2001-11-27

申请号：US09028065

申请日：1998-02-23

申请人： Sanjeev Khanna ,  Shanmugavelayut Muthukrishnan

发明人： Sanjeev Khanna ,  Shanmugavelayut Muthukrishnan

IPC分类号： G06F900

CPC分类号： G06T17/20 ,  Y10S707/99931 ,  Y10S707/99933 ,  Y10S707/99943

摘要： A method and apparatus for determining an approximated solution to the partitioning of a two or greater dimensional array in an amount of time on the order of O(1). Given a desired maximum weight or a maximum number of partitions, an array of data is partitioned by determining a temporary division of the array of blocks such that each block has a weight of at least two times the desired maximum weight. Within each block, rectangles are determined which contain array elements greater than or equal to an arbitrary value corresponding to a guess at a maximum weight. From among these rectangles, a largest set of independent rectangles is determined, and partitions are defined based on the sides of the largest set of independent rectangles determined for each block. Select ones of the partitions may be deleted until a total number of defined partitions is equal to or less than a desired maximum number of partitions.

摘要翻译： 用于确定在O（1）量级上的时间量的二维或更大尺寸阵列的分割的近似解的方法和装置。 给定期望的最大权重或最大数量的分区，通过确定块的阵列的临时划分使得每个块具有至少是所需最大权重的两倍的权重来划分数据数组。 在每个块内，确定包含大于或等于对应于最大权重的猜测的任意值的数组元素的矩形。 从这些矩形中，确定最大的独立矩形集合，并且基于为每个块确定的最大独立矩形集合的侧面来定义分区。 可以删除选择的分区，直到定义的分区的总数等于或小于期望的最大分区数。

公开(公告)号：US06185220B2

公开(公告)日：2001-02-06

申请号：US09097878

申请日：1998-06-15

申请人： Shanmugavelayut Muthukrishnan ,  Suleyman Cenk Sahinalp ,  Michael S. Paterson

发明人： Shanmugavelayut Muthukrishnan ,  Suleyman Cenk Sahinalp ,  Michael S. Paterson

IPC分类号： H04L1228

CPC分类号： H04L12/5601 ,  G06F17/5068 ,  H04L49/106 ,  H04L49/256 ,  H04L49/405 ,  H04L2012/561 ,  H04Q11/0478

摘要： A systematic method for creating layouts for various sorting and switching networks on VLSI chips is proposed. These sorting and switching networks include butterfly switching networks, benes networks, odd-even sorting networks, and bitonic sorting networks. The present invention utilizes the existing VLSI grid-model to create various layouts. A rectangular layout is proposed which introduces the use of an additional row to create an area-efficient layout for various switching networks. A diamond layout is proposed which further improves rectangular layout by reducing the number of columns required. A suitable combination of diamond and rectangular layouts is also proposed.

摘要翻译： 提出了一种用于在VLSI芯片上为各种排序和交换网络创建布局的系统方法。 这些分类和交换网络包括蝶形交换网络，蜂窝网络，奇偶分类网络和比特分类网络。本发明利用现有的VLSI网格模型来创建各种布局。 提出了一种矩形布局，其引入使用附加行来为各种交换网络创建面积效率的布局。 提出了一种钻石布局，通过减少所需列数来进一步改善矩形布局。 还提出了金刚石和矩形布局的合适组合。

公开(公告)号：US6052689A

公开(公告)日：2000-04-18

申请号：US62589

申请日：1998-04-20

申请人： Shanmugavelayut Muthukrishnan ,  Viswanath Poosala ,  Torsten Suel

发明人： Shanmugavelayut Muthukrishnan ,  Viswanath Poosala ,  Torsten Suel

IPC分类号： G06F17/30

CPC分类号： G06F17/30536 ,  Y10S707/99932 ,  Y10S707/99942

摘要： A computer method, apparatus and programmed medium for optimizing the number of buckets, and thus minimizing the necessary amount of memory space, needed to construct a histogram of a data distribution contained within a computer database with a cumulative error bounded by a specified threshold. The method according to the present invention allows a user to determine the near-minimal memory space necessary to store an approximation of a database with a maximum error measure at most three times that specified by the user to allow the user to maximize computer resources.

摘要翻译： 一种计算机方法，设备和编程介质，用于优化桶的数量，从而最小化必需的存储器空间量，以构成包含在具有由特定阈值限定的累积误差的计算机数据库内的数据分布的直方图。 根据本发明的方法允许用户确定存储数据库近似值所需的近似最小存储器空间，其中最大误差量度最多为用户指定的三倍，以允许用户最大化计算机资源。

公开(公告)号：US20070255748A1

公开(公告)日：2007-11-01

申请号：US11783288

申请日：2007-04-06

申请人： Paolo Ferragina ,  Fabrizion Luccio ,  Giovanni Manzini ,  Shanmugavelayut Muthukrishnan

发明人： Paolo Ferragina ,  Fabrizion Luccio ,  Giovanni Manzini ,  Shanmugavelayut Muthukrishnan

IPC分类号： G06F7/00

CPC分类号： G06F17/30961

摘要： A method of structuring and compressing labeled trees of arbitrary degree and shape for optimal succinctness, the method including a transform for compressing and indexing tree shaped data, using path sorting and grouping to linearize labeled tree shaped data into two coordinated arrays, one capturing the structure of the tree and the other capturing the labels of the tree. Additional navigational operations and basic searching may be performed on the transformed data.

摘要翻译： 一种构造和压缩任意程度和形状的标准树以实现最佳简洁度的方法，该方法包括用于压缩和索引树形数据的变换，使用路径排序和分组将标记的树状数据线性化成两个协调的阵列，一个捕获结构 的树，另一个捕获树的标签。 可以对转换的数据执行附加的导航操作和基本搜索。