Patent application number | Description | Published |
20090319726 | Efficient Region Coherence Protocol for Clustered Shared-Memory Multiprocessor Systems - A system and method of a region coherence protocol for use in Region Coherence Arrays (RCAs) deployed in clustered shared-memory multiprocessor systems which optimize cache-to-cache transfers by allowing broadcast memory requests to be provided to only a portion of a clustered shared-memory multiprocessor system. Interconnect hierarchy levels can be devised for logical groups of processors, processors on the same chip, processors on chips aggregated into a multichip module, multichip modules on the same printed circuit board, and for processors on other printed circuit boards or in other cabinets. The present region coherence protocol includes, for example, one bit per level of interconnect hierarchy, such that the one bit has a value of “1” to indicate that there may be processors caching copies of lines from the region at that level of the interconnect hierarchy, and the one bit has a value of “0” to indicate that there are no cached copies of any lines from the region at that respective level of the interconnect hierarchy. | 12-24-2009 |
20090327619 | Access Speculation Predictor with Predictions Based on Memory Region Prior Requestor Tag Information - An access speculation predictor may predict whether to perform speculative retrieval of data for a data request from a main memory based on whether or not a current requestor tag matches a previous requestor tag. In particular, a first address and a first requester tag may be extracted from a first data request and a finite state machine (FSM) of a memory controller may be selected whose memory region includes the first address. A second requester tag, that identifies a previous requester that attempted to access the memory region association with the selected FSM, may be retrieved from a register associated with the selected FSM and compared to the first requester tag. Speculatively retrieving the data for the first data request from a main memory may be controlled based on results of the comparison of the first requester tag to the second requester tag. | 12-31-2009 |
20100005242 | Efficient Processing of Data Requests With The Aid Of A Region Cache - A method and system for configuring a cache memory system in order to efficiently process processor requests. A group of cache elements, which include a Region Cache, a Region Coherence Array, and a lowest level cache, is configured based on a tradeoff of latency and power consumption requirements. A selected cache configuration differs from other feasible configurations in the order in which cache elements are accessed relative to each other. The Region Cache is employed in a number of configurations to reduce the power consumption, latency, and bandwidth requirements of the Region Coherence Array. The Region Cache is accessed by processor requests before (or in parallel with) the larger Region Coherence Array, providing the region coherence state and power efficiently to requests that hit in the Region Cache. | 01-07-2010 |
20100023698 | Enhanced Coherency Tracking with Implementation of Region Victim Hash for Region Coherence Arrays - A method and system for precisely tracking lines evicted from a region coherence array (RCA) without requiring eviction of the lines from a processor's cache hierarchy. The RCA is a set-associative array which contains region entries consisting of a region address tag, a set of bits for the region coherence state, and a line-count for tracking the number of region lines cached by the processor. Tracking of the RCA is facilitated by a non-tagged hash table of counts represented by a Region Victim Hash (RVH). When a region is evicted from the RCA, and lines from the evicted region still reside in the processor's caches (i.e., the region's line-count is non-zero), the RCA line-count is added to the corresponding RVH count. The RVH count is decremented by the value of the region line count following a subsequent processor cache eviction/invalidation of the region previously evicted from the RCA. | 01-28-2010 |
20100131439 | BIT-SELECTION FOR STRING-BASED GENETIC ALGORITHMS - Selecting bits in a string-based genetic algorithm is provided. A type of genetic operation to perform is determined. Responsive to a determination to perform a crossover operation, an input comprising a pair of strings is received. The strings in the pair of strings are compared to identify a set of non-matching points. A set of points from the set of non-matching points is randomly selected, forming a set of randomly selected non-matching points. A new string for the pair of strings is generated using the set of randomly selected non-matching points. | 05-27-2010 |
20100281220 | Predictive ownership control of shared memory computing system data - A method, circuit arrangement, and design structure utilize a lock prediction data structure to control ownership of a cache line in a shared memory computing system. In a first node among the plurality of nodes, lock prediction data in a hardware-based lock prediction data structure for a cache line associated with a first memory request is updated in response to that first memory request, wherein at least a portion of the lock prediction data is predictive of whether the cache line is associated with a release operation. The lock prediction data is then accessed in response to a second memory request associated with the cache line and issued by a second node and a determination is made as to whether to transfer ownership of the cache line from the first node to the second node based at least in part on the accessed lock prediction data. | 11-04-2010 |
20100281221 | Shared Data Prefetching with Memory Region Cache Line Monitoring - A method, circuit arrangement, and design structure for prefetching data for responding to a memory request, in a shared memory computing system of the type that includes a plurality of nodes, is provided. Prefetching data comprises, receiving, in response to a first memory request by a first node, presence data for a memory region associated with the first memory request from a second node that sources data requested by the first memory request, and selectively prefetching at least one cache line from the memory region based on the received presence data. Responding to a memory request comprises tracking presence data associated with memory regions associated with cached cache lines in the first node, and, in response to a memory request by a second node, forwarding the tracked presence data for a memory region associated with the memory request to the second node. | 11-04-2010 |
20110302374 | LOCAL AND GLOBAL MEMORY REQUEST PREDICTOR - A method, circuit arrangement, and design structure utilize broadcast prediction data to determine whether to globally broadcast a memory request in a computing system of the type that includes a plurality of nodes, each node including a plurality of processing units. The method includes updating broadcast prediction data for a cache line associated with a first memory request within a hardware-based broadcast prediction data structure in turn associated with a first processing unit in response to the first memory request, the broadcast prediction data for the cache line including data associated with a history of ownership of the cache line. The method further comprises accessing the broadcast prediction data structure and determining whether to perform an early broadcast of a second memory request to a second node based on broadcast prediction data within the broadcast prediction data structure in response to that second memory request associated with the cache line. | 12-08-2011 |
20120151297 | Enhanced Coherency Tracking with Implementation of Region Victim Hash for Region Coherence Arrays - A method and system for precisely tracking lines evicted from a region coherence array (RCA) without requiring eviction of the lines from a processor's cache hierarchy. The RCA is a set-associative array which contains region entries consisting of a region address tag, a set of bits for the region coherence state, and a line-count for tracking the number of region lines cached by the processor. Tracking of the RCA is facilitated by a non-tagged hash table of counts represented by a Region Victim Hash (RVH). When a region is evicted from the RCA, and lines from the evicted region still reside in the processor's caches (i.e., the region's line-count is non-zero), the RCA line-count is added to the corresponding RVH count. The RVH count is decremented by the value of the region line count following a subsequent processor cache eviction/invalidation of the region previously evicted from the RCA. | 06-14-2012 |
20120265942 | PREDICTIVE OWNERSHIP CONTROL OF SHARED MEMORY COMPUTING SYSTEM DATA - A method, circuit arrangement, and design structure utilize a lock prediction data structure to control ownership of a cache line in a shared memory computing system. In a first node among the plurality of nodes, lock prediction data in a hardware-based lock prediction data structure for a cache line associated with a first memory request is updated in response to that first memory request, wherein at least a portion of the lock prediction data is predictive of whether the cache line is associated with a release operation. The lock prediction data is then accessed in response to a second memory request associated with the cache line and issued by a second node and a determination is made as to whether to transfer ownership of the cache line from the first node to the second node based at least in part on the accessed lock prediction data. | 10-18-2012 |
Patent application number | Description | Published |
20100191914 | REGION COHERENCE ARRAY HAVING HINT BITS FOR A CLUSTERED SHARED-MEMORY MULTIPROCESSOR SYSTEM - A system and method for a multilevel region coherence protocol for use in Region Coherence Arrays (RCAs) deployed in clustered shared-memory multiprocessor systems which optimize cache-to-cache transfers (interventions) by using region hint bits in each RCA to allow memory requests for lines of a region of the memory to be optimally sent to only a determined portion of the clustered shared-memory multiprocessor system without broadcasting the requests to all processors in the system. A sufficient number of region hint bits are used to uniquely identify each level of the system's interconnect hierarchy to optimally predict which level of the system likely includes a processor that has cached copies of lines of data from the region. | 07-29-2010 |
20100191921 | REGION COHERENCE ARRAY FOR A MULT-PROCESSOR SYSTEM HAVING SUBREGIONS AND SUBREGION PREFETCHING - A Region Coherence Array (RCA) having subregions and subregion prefetching for shared-memory multiprocessor systems having a single-level, or a multi-level interconnect hierarchy architecture. | 07-29-2010 |
20110161264 | OPTIMIZED SEEDING OF EVOLUTIONARY ALGORITHM BASED SIMULATIONS - Seed candidate solutions can be inserted into the later generations of the population of an optimization problem during an evolutionary algorithm based simulation. Seed candidate solutions can be determined in response to an evolutionary algorithm based simulator receiving a problem description of an optimization problem. The seed candidate solutions can be sorted according to the seed candidate solutions' fitness. The simulator can start an evolutionary algorithm based simulation with a randomly generated initial population. The simulator can detect a condition for inserting seed candidate solutions into the population. The simulator can then insert the first seed candidate into the current population that is generated by the simulator in accordance with the evolutionary algorithm. A solution to the optimization problem can be determined based on successive generation of candidate solutions and insertion of additional seed candidate solutions in subsequent generations of the population. | 06-30-2011 |
20120005136 | PERFORMING CONSTRAINT COMPLIANT CROSSOVERS IN POPULATION-BASED OPTIMIZATION - Some embodiments are directed to determining a plurality of constraint compliant values for each of a plurality of constrained variables of an optimization problem, wherein the plurality of constraint compliant values comply with a constraint condition that constrains possible values that can be used for the plurality of constrained variables; generating a population of constraint compliant candidate solutions for a computer-based simulation that implements a population-based optimization algorithm for the optimization problem, wherein the constraint compliant candidate solutions use a subset of the plurality of constraint compliant values and each of the constraint compliant candidate solutions comply with the constraint condition; while running the computer-based simulation with the population of constraint compliant candidate solutions, determining that a child candidate solution created from two of the constraint compliant candidate solutions fails to comply with the constraint condition; and modifying the child candidate solution to use at least one value randomly selected from the plurality of constraint compliant values for a corresponding one of the plurality of constrained variables resulting in a modified child candidate solution that complies with the candidate solution. | 01-05-2012 |
20120005137 | GENERATING CONSTRAINT-COMPLIANT POPULATIONS IN POPULATION-BASED OPTIMIZATION - Some embodiments are directed to determining a plurality of sets of variables of an optimization problem, where a first set of the plurality of sets comprises a constrained variable constrained by a constraint condition indicated by a constraint description for the optimization problem and where a second set of the plurality of sets of variables comprises a non-constrained variable. Some embodiments are further directed to determining a plurality of constraint compliant values for the constrained variable that comply with the constraint condition and generating a plurality of non-constrained values for the non-constrained variable. Some embodiments are further directed to randomly combining individual ones of the plurality of constraint compliant values with individual ones of the plurality of non-constrained values into a plurality of value sets that satisfy the constraint description for the optimization problem. Some embodiments are further directed to running a computer based simulation that implements a population-based optimization algorithm with the plurality of value sets input as a population for the computer-based simulation. | 01-05-2012 |
20120005138 | MODIFYING CONSTRAINT-COMPLIANT POPULATIONS IN POPULATION-BASED OPTIMIZATION - Some embodiments are directed to determining a plurality of constraint compliant values for each of a plurality of constrained variables of an optimization problem, wherein a constraint condition mutually constrains possible values that can be used for the plurality of constrained variables, and wherein the plurality of constraint compliant values comply with the constraint condition. Some embodiments are further directed to generating a population of constraint compliant candidate solutions for a computer-based simulation that implements a population-based optimization algorithm for the optimization problem, wherein the constraint compliant candidate solutions use a subset of the plurality of constraint compliant values and each of the constraint compliant candidate solutions comply with the constraint condition. Some embodiments are further directed to, while running the computer-based simulation with the population of constraint compliant candidate solutions, determining that a mutated candidate solution created from mutating one of the constraint compliant candidate solutions fails to comply with the constraint condition. Some embodiments are further directed to modifying the mutated candidate solution to use at least one value randomly selected from the plurality of constraint compliant values for a corresponding one of the plurality of constrained variables resulting in a constraint compliant mutated candidate solution that complies with the constraint condition. | 01-05-2012 |
20120130928 | EFFICIENT STORAGE OF INDIVIDUALS FOR OPTIMIZATION SIMULATION - Candidate solutions to an optimization problem comprise a set of potential values that can be applied to variables in a problem description. Candidate solutions can be large because of the complexity of optimization problems and large number of variables. The populations of candidate solutions may also be large to ensure diversity and effectiveness in computing a solution. When the populations and the candidate solutions are large for an optimization problem, computing a solution to the optimization problem consumes a large amount of memory. In some instances, several generations of candidate solutions are stored in memory. Compression of the candidate solutions can minimize the memory space consumed to compute a solution to an optimization problem. | 05-24-2012 |
20120130929 | CONTROLLING QUARANTINING AND BIASING IN CATACLYSMS FOR OPTIMIZATION SIMULATIONS - Some embodiments are directed to generating a first probability value that represents a percentage of times that first bit values for a given bit position of a first plurality of candidate solutions equate to a pre-defined number, where the first plurality of candidate solutions has converged on a sub-optimal solution during a simulation of an optimization problem using an optimization algorithm. Some embodiments are further directed to generating a second probability value that is inversely biased from the first probability value; and generating a second plurality of candidate solutions with the second probability value, where the second plurality of candidate solutions are inversely biased from the first bit values for the given bit position. | 05-24-2012 |
20130006901 | SPECULATIVE ASYNCHRONOUS SUB-POPULATION EVOLUTIONARY COMPUTING - A tool computes fitness values for a first generation of a first sub-population of a plurality of sub-populations. A population of candidate solutions for an optimization problem was previously divided into the plurality of sub-populations. The population of candidate solutions was created for an iterative computing process in accordance with an evolutionary algorithm to identify a most fit candidate solution for the optimization problem. The tool determines a speculative ranking of the first generation of the first sub-population prior to the fitness values being computed for all candidate solutions in the first generation of the first sub-population. The tool generates a next generation of the first sub-population based, at least in part, on the speculative ranking prior to completion of computation of the fitness values for the first generation of the first sub-population. | 01-03-2013 |
20130006902 | SPECULATIVE ASYNCHRONOUS SUB-POPULATION EVOLUTIONARY COMPUTING - A tool computes fitness values for a first generation of a first sub-population of a plurality of sub-populations. A population of candidate solutions for an optimization problem was previously divided into the plurality of sub-populations. The population of candidate solutions was created for an iterative computing process in accordance with an evolutionary algorithm to identify a most fit candidate solution for the optimization problem. The tool determines a speculative ranking of the first generation of the first sub-population prior to the fitness values being computed for all candidate solutions in the first generation of the first sub-population. The tool generates a next generation of the first sub-population based, at least in part, on the speculative ranking prior to completion of computation of the fitness values for the first generation of the first sub-population. | 01-03-2013 |
20130007425 | PROCESSOR AND DATA PROCESSING METHOD INCORPORATING AN INSTRUCTION PIPELINE WITH CONDITIONAL BRANCH DIRECTION PREDICTION FOR FAST ACCESS TO BRANCH TARGET INSTRUCTIONS - Disclosed are a processor and a processing method incorporating an instruction pipeline with direction prediction (i.e., taken or not taken) for conditional branch instructions. In the embodiments, reading of a branch instruction history table (BHT) and a branch instruction target address cache (BTAC) for branch direction prediction occurs in parallel with the current instruction fetch in order to minimize delay in the next instruction fetch. Additionally, direction prediction is performed in the very next clock cycle based either on an initial direction prediction for the specific instruction, as stored in the BHT, or, if applicable, on a prior entry for the specific instruction in the BTAC. An override bit associated with each entry in the BTAC is the determining factor for whether or the BTAC or BHT is controlling. Override bits in the BTAC can be pre-established based on the branch instruction type in order to ensure prediction accuracy. | 01-03-2013 |
20130173511 | USING GLOBAL AND LOCAL CATASTROPHES ACROSS SUB-POPULATIONS IN PARALLEL EVOLUTIONARY COMPUTING - A parallel genetic algorithm computing process tracks forward progress of a first sub-population across generations thereof. The first sub-population is one of a plurality of sub-populations that form a population of candidate solutions to an optimization problem. At a current generation of the first sub-population, it is determined that forward progress of the first sub-population fails a set of one or more forward progress criteria. In response to determining that the forward progress of the first sub-population fails the set of one or more forward progress criteria at the current generation, a local catastrophe is invoked on the current generation of the first sub-population. The first sub-population is re-populated after the local catastrophe is invoked. The first sub-population is re-established after re-populating while constraining migration to the first sub-population. | 07-04-2013 |
20130173512 | USING GLOBAL AND LOCAL CATASTROPHES ACROSS SUB-POPULATIONS IN PARALLEL EVOLUTIONARY COMPUTING - A parallel genetic algorithm computing process tracks forward progress of a first sub-population across generations thereof. The first sub-population is one of a plurality of sub-populations that form a population of candidate solutions to an optimization problem. At a current generation of the first sub-population, it is determined that forward progress of the first sub-population fails a set of one or more forward progress criteria. In response to determining that the forward progress of the first sub-population fails the set of one or more forward progress criteria at the current generation, a local catastrophe is invoked on the current generation of the first sub-population. The first sub-population is re-populated after the local catastrophe is invoked. The first sub-population is re-established after re-populating while constraining migration to the first sub-population. | 07-04-2013 |
20130226848 | MODIFYING CONSTRAINT-COMPLIANT POPULATIONS IN POPULATION-BASED OPTIMIZATION - An example system and process with some operations that include determining a plurality of values, wherein assignment of any of the plurality of values to one or more constrained variables of a candidate solution causes the candidate solution to comply with a constraint condition of an optimization problem, wherein the candidate solution complies with the constraint condition prior to being mutated via a computer-based simulation that tests fitness of the candidate solution. The operations further include after the candidate solution is mutated, determining that the candidate solution fails to comply with the constraint condition. The operations further include assigning at least one value, which is randomly selected from the plurality of values, to the one or more constrained variables of the candidate solution. | 08-29-2013 |
20130232096 | PERFORMING CONSTRAINT COMPLIANT CROSSOVERS IN POPULATION-BASED OPTIMIZATION - An example system and process with some operations that include determining a plurality of constraint compliant values and determining that a candidate solution, which was created from two or more of a plurality of candidate solutions via a crossover operation, fails to comply with a constraint condition for an optimization problem, wherein the two or more of the plurality of candidate solutions comply with the constraint condition. In some examples, the operations further include assigning a value from the plurality of constraint compliant values to a constrained variable of the candidate solution in response to the determining that the candidate solution fails to comply with the constraint condition, wherein the value assigned from the plurality of constraint compliant values is randomly selected from the plurality of constraint compliant values, and wherein the at least one constrained variable is constrained to comply with the constraint condition. | 09-05-2013 |
20130238537 | GENERATING CONSTRAINT-COMPLIANT POPULATIONS IN POPULATION-BASED OPTIMIZATION - An example system and process where some operations include determining that a plurality of values satisfy one or more constraint conditions for an optimization problem. The operations further include randomly selecting a set of one or more values from the plurality of values after determining that the plurality of values satisfy the one or more constraint conditions. The operations further include including the set of one or more values in a candidate solution for the optimization problem. The including the set of one or more values in the candidate solution causes the candidate solution to comply with the one or more constraint conditions for the optimization problem prior to running a computer based simulation for the optimization problem. | 09-12-2013 |
20130275351 | CONTROLLING QUARANTINING AND BIASING IN CATACLYSMS FOR OPTIMIZATION SIMULATIONS - Some examples are directed to determining a frequency of occurrence of a first value in a component of a first plurality of candidate solutions for an optimization problem where the first plurality of candidate solutions has converged on a sub-optimal solution during a computer simulation that tests fitness of the first plurality of candidate solutions. Some examples are further directed to determining a second value that is inversely biased from the frequency of occurrence of the first value. Some examples are further directed to including the second value in a component of at least a portion of a second plurality of candidate solutions, where the component of the at least the portion of the second plurality of candidate solutions corresponds to the component of the first plurality of candidate solutions. | 10-17-2013 |
20140279765 | EARLY GENERATION OF INDIVIDUALS TO ACCELERATE GENETIC ALGORITHMS - While at least one candidate solution of a first generation of candidate solutions remains to be evaluated in accordance with a fitness function for an optimization problem, a plurality of candidate solutions is selected from the first generation of candidate solutions to participate in a tournament. It is determined whether each of the plurality of candidate solutions selected to participate in the tournament have been evaluated in accordance with the fitness function. If all have been evaluated, then one or more winners of the tournament are selected from the plurality of candidate solutions of the first generation of candidate solutions. A candidate solution of a second generation of candidate solutions is created with the selected one or more winners of the tournament in accordance with a genetic operator. | 09-18-2014 |
20140344196 | ADAPTIVE CATACLYSMS IN GENETIC ALGORITHMS - It is determined that a population of candidate solutions for an optimization problem has prematurely converged during a metaheuristic optimization run. A cause for premature convergence of the population is determined based, at least in part, on an analysis of the metaheuristic optimization run. A first cataclysm strategy of a plurality of cataclysm strategies is selected based, at least in part, on one of the cause of the premature convergence and a history of the metaheuristic optimization run. A cataclysm is simulated based, at least in part, on the first cataclysm strategy. | 11-20-2014 |
20140344197 | ADAPTIVE CATACLYSMS IN GENETIC ALGORITHMS - It is determined that a population of candidate solutions for an optimization problem has prematurely converged during a metaheuristic optimization run. A cause for premature convergence of the population is determined based, at least in part, on an analysis of the metaheuristic optimization run. A first cataclysm strategy of a plurality of cataclysm strategies is selected based, at least in part, on one of the cause of the premature convergence and a history of the metaheuristic optimization run. A cataclysm is simulated based, at least in part, on the first cataclysm strategy. | 11-20-2014 |
20140344199 | CONTROLLING QUARANTINING AND BIASING IN CATACLYSMS FOR OPTIMIZATION SIMULATIONS - Some examples are directed to selecting at least one candidate solution from a first plurality of candidate solutions that has converged on a suboptimal solution during a computer simulation. The computer simulation tests fitness of the first plurality of candidate solutions for an optimization problem. Some examples are further direct to storing a copy of the at least one candidate solution, performing a cataclysm on the first plurality of candidate solutions, and generating a second plurality of candidate solutions. Some examples are further direct to integrating the copy of the at least one candidate solution into the second plurality of candidate solutions after performing of one or more additional computer simulations that test the fitness of the second plurality of candidate solutions for the optimization problem. | 11-20-2014 |
20150046379 | GUIDING METAHEURISTIC TO SEARCH FOR BEST OF WORST - Figures of merit by actual design parameters are tracked over iterations for candidate solutions that include both actual design parameters and actual context parameters. Instead of returning a current iteration figure of merit, a worst observed figure of merit for a set of actual design parameters is returned as the figure of merit for a candidate solution. Since the candidate solution includes both actual design parameters and actual context parameters and the worst observed figures of merit are tracked by actual design parameters, the figure of merit for a set of design parameters wilt be the worst of the observed worst case scenarios as defined by the actual context parameters over a run of a metaheuristic optimizer. | 02-12-2015 |
20150046380 | GUIDING METAHEURISTIC TO SEARCH FOR BEST OF WORST - Figures of merit by actual design parameters are tracked over iterations for candidate solutions that include both actual design parameters and actual context parameters. Instead of returning a current iteration figure of merit, a worst observed figure of merit for a set of actual design parameters is returned as the figure of merit for a candidate solution. Since the candidate solution includes both actual design parameters and actual context parameters and the worst observed figures of merit are tracked by actual design parameters, the figure of merit for a set of design parameters will be the worst of the observed worst case scenarios as defined by the actual context parameters over a run of a metaheuristic optimizer. | 02-12-2015 |