TWI470545B - Apparatus,processor,system,method,instruction,and logic for performing range detection - Google Patents

Description

Apparatus, processor, system, method, instruction, and logic for performing range detection

The specific embodiments of the present invention are generally related to the field of information processing, and more particularly to the field of performing range detection in computing systems and microprocessors.

The performance of computer hardware, such as mathematical functions in a microprocessor, can be determined by the use of some locations, such as cache memory or lookup tables (LUTs) stored in the main memory. A single instruction majority (SIMD) instruction can perform most memory operations to access LUTs in hardware when executing mathematical functions. For example, for each of a number of input operands, a SIMD instruction executing a function based on the input operands can access a LUT to obtain a result output for the SIMD function, as some processor architectures do not provide for a number of LUTs. Parallel access, but conversely using the same memory access logic to access one or more LUTs, these LUT accesses may occur in series, rather than in a parallel manner, thereby limiting execution of the SIMD function Performance.

Mathematical functions can be evaluated in some algorithms using curve equations or other polynomial-based techniques. In some prior art examples, the curve equation function used to evaluate mathematical functions requires a majority of software operations to perform targets such as range detection, coefficient matching, and polynomial calculations. The use of curve equations to evaluate mathematical functions can therefore be computationally intensive and relatively low in performance, thus limiting the usefulness of curve equation calculations in computer programs.

SUMMARY OF THE INVENTION AND EMBODIMENT

Particular embodiments of the present invention can be used to improve the mathematical performance of microprocessors and computers. In some embodiments, the curve equation calculations can be used to perform various mathematical operations at a higher performance level than some prior art curve equations. In at least one embodiment, the curve equation calculation performance can be improved by accelerating at least one of the most time consuming and resource consuming operations involved in the calculation of the curve equation. In one embodiment, a range detection command and corresponding hardware logic are provided to detect the acceleration range within the curve equation, which corresponds to the various polynomials used in the calculation of the curve equation.

Figure 1 illustrates a microprocessor in which at least one embodiment of the present invention can be utilized. In particular, Figure 1 illustrates a microprocessor 100 having one or more processor cores 105 and 110, each associated with a local cache memory 107 and 113, respectively. Also illustrated in FIG. 1 is a shared cache memory 115 that stores a version of at least a portion of the information stored in each of the local cache memories 107 and 113. In some embodiments, the microprocessor 100 can also include another logic not shown in FIG. 1, such as an integrated memory controller, an integrated graphics controller, and another logic in a computer system. Perform other functions such as input/output control. In one embodiment, each of the microprocessors or multi-core processors in the multi-processor system may include logic 119 or otherwise associated with logic 119 to Embodiments respond to an instruction execution range detection.

2 illustrates a front side busbar (FSB) computer system in which a particular embodiment of the present invention can be used. In one of the processor cores 223, 227, 233, 237, 243, 247, 253, 257 or otherwise associated with the processor core, any processor 201, 205, 210 or 215 can be any local The first-order (L1) cache memory 220, 225, 230, 235, 240, 245, 250, 255 accesses information. Moreover, any processor 201, 205, 210 or 215 can access information via any of the shared second-order (L2) caches 203, 207, 213, 217 or from system memory 260 via chipset 265. One or more of the processors in FIG. 2 may include logic 219 or otherwise be associated with logic 219 to perform a range of detection instructions in accordance with a particular embodiment.

In addition to the FSB computer system illustrated in Figure 2, other system configurations can be utilized with various embodiments of the present invention, including point-to-point (P2P) interconnect systems and ring interconnect systems. The P2P system of FIG. 3 can include, for example, a number of processors, and for example, only two of the processors 370, 380 are shown. Each of the processors 370, 380 can include a local memory controller hub (MCH) 372, 382 for connection to the memory 32, 34. Processors 370, 380 can exchange data using PtP interface circuitry 378, 388 via point-to-point (PtP) interface 350. Each of the processors 370, 380 can exchange data with a chipset 390 via the individual PtP interfaces 352, 354 using point-to-point interface circuits 376, 394, 386, 398. The chipset 390 can also exchange data with a high performance graphics circuit 338 via a high performance graphics interface 339. Particular embodiments of the invention may be located in any processor having any number of processing cores, or within each PtP bus agent of FIG. In one embodiment, any processor core may include or otherwise be associated with a local cache memory (not shown). Furthermore, a shared cache memory (not shown) can be included in any processor external to both processors and connected to the processors via a p2p interconnect such that if a processor is placed into a processor In the low power mode, the local cache memory information of the one or two processors can be stored in the shared cache memory. One or more of the processors or cores of FIG. 3 may include logic 319 or otherwise be associated with logic 319 to perform a range of detection instructions in accordance with a particular embodiment.

Curve equation calculations negate the need to use lookup tables (LUTs) and the expensive memory access associated with them. Figure 4 illustrates the first-order curve equation function. In Figure 4, let "X" be a 8 element input vector whose elements include data, 256 bits in the vector X, and "Xin" each represented by 32 bits. For any given input "Xin", the element "Yout" of the vector Y of the curve equation function may result in a vector W = Y(X). The elements of the vector W can be evaluated using a curve equation calculation operation including range detection, coefficient matching, and polynomial calculation. At least one embodiment includes an instruction and logic to evaluate execution range detection in the curve equation function. In some embodiments, the element size of vector X can be 8 bits, however, in other embodiments, they can be 16 bits, 32 bits, 64 bits, 128 bits, and the like. Moreover, in some embodiments, the elements of X may be integers, floating point values, single or double precision floating point values, and the like.

In a specific embodiment, the range detection logic can include decoding and execution logic to execute a range detection instruction having an instruction format, and control the field to perform the representation, "Range Vector (R) = Range_Detection (Input Vector) (X), Range Limit Vector (RL)), where R is a range vector generated by the logic described in Figure 5, X is the input vector, and RL is each of the curve equation functions The vector of the first Xin of the range. For example, in one embodiment, the vector RL includes a first Xin (0, 10, 30, 50, 70, 80, 255) for each range of FIG. 4, corresponding to the input vector X in some order.

In one embodiment, a range of matching curve function functions illustrated in FIG. 4 is detected based on each input point provided within the input vector X, and the result is stored in a SIMD register. The following example shows an input vector X and a range detector vector corresponding to the curve equation described in FIG. The given example describes the operation on a 16-bit fixed-point input; however, the same technique can be applied to 8- and 32-bit fixed and floating-point values, as well as different data used in current and future vector extensions. Type.

Let X be the following input vector, where each element contains a Xin value along the x-axis of Figure 4:

Based on the above input vector X and the curve equation depicted in Figure 4, the range detection vector will contain the following:

In one embodiment, an instruction can be executed to generate the above range detection vector by operation on the input vector according to the curve equation of FIG. In one embodiment, the instructions cause the input vector elements to be compared to each of the range limits (0, 10, 30, 50, 70, 80 in Figure 4). In one embodiment, each range limit can be propagated to and compared to the SIMD register. In a specific embodiment, the comparison operation results in 0 or -1 to indicate the result of the comparison, and the subtraction and accumulation of the comparison results yields a range of the curve equation, wherein each input of the input vector X Points are included. The logic for performing these comparison operations is illustrated in Figure 5, where x _i indicates an input point within the input vector X, t _i describes the range limit of the curve equation of Figure 4, and r _i describes the range detection vector R The range of results corresponds to the input point x _i . In other embodiments, the comparison operation may result in other values (eg, 1 and 0) that may be performed using the comparison, addition or subtraction, and accumulation of the comparison values to produce a range detection vector R.

Figure 5a illustrates logic that may be used to generate a range detection vector R in response to execution of a range detection instruction in accordance with a particular embodiment. In one embodiment, logic 500a includes an input vector X501a that is compared to range limit vector 510a by comparison logic 505a, which includes a range limit for each curve element corresponding to the range of the input vector X. i" elements. In one embodiment, an element of input vector 501a is compared by a comparison element 505a with a corresponding element of range limit vector 510a. In one embodiment, the element of zero vector 515a adds 517a to the negative of the comparison of input vector 501a and range limit vector 510a to produce 0 or -1 in each element of the result of the comparison. The input vector 501a is then compared to the corresponding element of the range limit vector 520a, and the negative result is added to the previous comparison result. This process continues for each element of the range limit vector 510a, ending in the range detection vector 525a.

In one embodiment, the logic of FIG. 5a may be used by the same program using at least one instruction set architecture and illustrated by the following virtual code:

Other techniques for determining the range detection vector R can be used in other embodiments, including logic to perform binary search on the range of restricted vector elements. Figure 5b illustrates a binary search dendrogram, which may be used to generate a range detection vector R, according to a particular embodiment. In the binary search bar graph 500b of FIG. 5b, each element of the input vector X501b is compared with each element 510b of the range restriction vector, in an intermediate vector element (T4, at the 8-element input and range limit vector In the case of the case, start and continue to each half vector (T5-T8, and T3-T1). In one embodiment, the following virtual code illustrates the effect of the binary search for the dendrogram of Figure 5b and uses instructions from an indicator set architecture.

In the above virtual code, T represents the range limit vector, and I represents the i-th element of the input vector X and the range limit vector T.

In one embodiment, an instruction and corresponding logic are used to generate the range detection vector R. When the range detection vector R is determined, other operations associated with evaluating the curve equation function can be performed, the function being associated with the particular mathematical operation in question, including the coefficient matching and polynomial calculation operations.

In one embodiment, each polynomial of each range corresponding to the equation of the curve in FIG. 4 has a corresponding coefficient. Coefficient matching matches coefficient vector elements to range detection vector elements produced in a particular embodiment of the invention. In the example illustrated in Figure 4, there are six ranges, which can be described by the following polynomial:

Range 1: y=2*x (0<=X<10)

Range 2: y=0*x+20 (10<=X<30)

Range 3: y=-2*x+20 (30<=X<50)

Range 4: y=0*x-20 (50<=X<70)

Range 5: y=2*x-20 (70<=X<80)

Range 6: y = 0 (80 <= X < 255)

The coefficient matching is based on the results of the range detection phase. The number of coefficient vectors for this result is equal to the highest number of times the polynomial is +1. Continuing the above example, the coefficient vectors C ₁ and C ₂ for the results of the input vector X described in FIG. 4 are described below:

The number of times of all polynomials in the above example is one, so the number of result coefficient vectors is two. In a specific embodiment, the C ₁ and C ₂ vectors are calculated using an output command based on the output of the range detection phase described in FIGS. 5a and 5b, which corresponds to the two coefficient vectors C ₁ and C ₂ . The appropriate coefficient is stored in the element.

After calculating the coefficients of the polynomial corresponding to the input vector X, the polynomial evaluation calculation can be performed for each of the input vectors X. In one embodiment, the polynomial calculation can be divided into two main operations. The first operation includes finding that each input value is offset by the beginning of the range of the curve equation. In one embodiment, the offsets are found to be achieved by, for example, using a blending instruction to match the beginning of each range to each input point. The offset from the beginning of each range of the curve equation of Figure 4 is then calculated by subtracting the initial value of each range from the corresponding input vector element. For example, point 77 in the curve equation of Figure 4 will be assigned to range 5. Since the start of range 5 is at 70, the offset from the beginning of its dispatch range is 7. The second operation includes calculating the output vector element for each input vector element. To calculate the final output vector, the offset found in the beginning of a range is found and set as an input element for the polynomial of interest. For example, the range 5 polynomial is described by the following formula: y = 2 * x -20. For this input vector element 77, we get the offset of 7 and the final value so used for point 77 would be y=2*(offset)-20=2*(7)-20=-6. After calculating the residual polynomials corresponding to the input vector elements, the results can be stored in a result vector. The vector value, offset vector value O, and output vector value Y for the initial range value B are described below:

The output vector Y is calculated by the expression according to a specific embodiment. In this example, the output vector Y is calculated by "Y=O*C1+C2".

Figure 6 illustrates a flow diagram of operations that may be used in conjunction with at least one embodiment of the present invention. In one embodiment, at operation 601, a range detection vector is generated. In one embodiment, the range detection vector is generated for each input vector element according to a process, such as the binary search and logic described herein. At operation 605, coefficient matching is performed to generate coefficients of polynomials corresponding to each range of the curve equation based on the input vector elements. At operation 610, a polynomial calculation is performed for each element in the input vector, and the result is stored in a result vector.

One or more aspects of at least one embodiment may be provided by representative material stored on a computer readable medium, the data representing various logic within the processor, when read by a machine The machine manufacturing logic is caused to perform the techniques described herein. Such representatives, known as "IP cores", can be stored on a physical, computer readable medium ("tape") and supplied to various customers or manufacturing equipment to load the logic or process that is actually made. Forming machine.

Thus, a method and apparatus for directing access to a micro-architectural memory region has been described. The above description is intended to be illustrative and not limiting. Many other specific embodiments will become apparent to those skilled in the art upon reading this description. Therefore, the scope of the invention will be determined with reference to the appended claims.

5. . . range

32. . . Memory

34. . . Memory

77. . . point

100. . . microprocessor

105. . . Processor core

107. . . Area cache memory

110. . . Processor core

113. . . Area cache memory

115. . . Shared cache memory

119. . . logic

201. . . processor

203. . . Cache memory

205. . . processor

207. . . Cache memory

210. . . processor

213. . . Cache memory

215. . . processor

217. . . Cache memory

219. . . logic

220. . . Cache memory

223. . . Processor core

225. . . Cache memory

227. . . Processor core

230. . . Cache memory

233. . . Processor core

235. . . Cache memory

237. . . Processor core

240. . . Cache memory

243. . . Processor core

245. . . Cache memory

247. . . Processor core

250. . . Cache memory

253. . . Processor core

255. . . Cache memory

257. . . Processor core

260. . . System memory

265. . . Chipset

319. . . logic

338. . . Drawing circuit

339. . . Drawing interface

350. . . Point-to-point interface

352. . . Point-to-point interface

354. . . Point-to-point interface

370. . . processor

372. . . Memory controller hub

376. . . Point-to-point interface circuit

378. . . Point-to-point interface circuit

380. . . processor

382. . . Memory controller hub

386. . . Point-to-point interface circuit

388. . . Point-to-point interface circuit

390. . . Chipset

394. . . Point-to-point interface circuit

394. . . Point-to-point interface circuit

500a‧‧‧Logic

500b‧‧‧ binary search for dendrites

501a‧‧‧ input vector

501b‧‧‧ input vector

505a‧‧‧Comparative logic

510a‧‧‧ Range Limit Vector

510b‧‧‧ elements

515a‧‧‧zero vector

520a‧‧‧ Range Limit Vector

525a‧‧‧ Range Restriction Vector

601‧‧‧ operation

605‧‧‧ operation

610‧‧‧ operation

C ₁ ‧ ‧ coefficient vector

C ₂ ‧‧‧ coefficient vector

I‧‧‧ elements

R‧‧‧ range detection vector

T‧‧‧ Range Limit Vector

T1‧‧‧ half vector

T2‧‧‧ half vector

T3‧‧‧ half vector

T4‧‧‧ intermediate vector element

T5‧‧‧ half vector

T6‧‧‧ half vector

T7‧‧‧ half vector

T8‧‧‧ half vector

X‧‧‧ input vector

The specific embodiments of the present invention are illustrated by way of example in the accompanying drawings, and not by way of limitation,

1 illustrates a block diagram of a microprocessor in which at least one embodiment of the present invention can be used;

2 illustrates a block diagram of a shared busbar computer system in which at least one embodiment of the present invention can be utilized;

3 illustrates a block diagram of a point-to-point interconnect computer system in which at least one embodiment of the present invention can be used;

Figure 4 illustrates a curve equation divided into regions according to an embodiment.

Figure 5 is a schematic diagram of logic that can be used to accelerate region detection within a curve equation in response to a region detection command in accordance with a particular embodiment.

6 is a flow diagram of operations that may be used to perform at least one embodiment of the present invention.

100. . . microprocessor

105. . . Processor core

107. . . Area cache memory

110. . . Processor core

113. . . Area cache memory

115. . . Shared cache memory

119. . . logic

Claims (23)

An apparatus for performing range detection, comprising: range detection logic, comprising: decoding logic to decode a range detection instruction to execute a single instruction multiple data from an input vector X and a range restriction vector T (single instruction multiple data) ; SIMD) range detection; and execution logic responsive to the range detection instruction to perform SIMD comparison to match the range of a curve equation function to each input point element of the input vector X and to accumulate the SIMD comparison result to produce a correspondence The range vector R includes a range of values of the curve equation function, including the corresponding input point of the input vector X, and storing the range vector R in a SIMD register. The device of claim 1, wherein the execution logic includes comparison logic to compare each element of the input vector with a corresponding range limit vector element. The device of claim 1, wherein the execution logic comprises binary search logic to compare each element of the input vector with a corresponding range limit vector element. The apparatus of claim 1, wherein the range detection logic includes a range vector storage to store the range vector including the range values. The device of claim 4, wherein the range detection logic comprises an input vector storage to store the input vector comprising the input point elements. The device of claim 5, wherein the device comprises at least one coefficient vector storage to store a complex coefficient vector element corresponding to the input vector elements. The device of claim 6, wherein the device includes at least one offset vector storage to store a plurality of offset vector elements corresponding to the input vector elements. The device of claim 7, wherein the device includes an output vector storage to store a plurality of output vector elements corresponding to the input vector elements. A method for performing range detection, comprising: performing range detection to generate a complex range value corresponding to a complex input value of a curve equation function; performing a coefficient matching operation to generate a complex coefficient corresponding to a complex polynomial, the complex polynomial Corresponding to an input value of the curve equation function; performing a polynomial evaluation calculation to generate a complex output value corresponding to the complex input value; wherein performing the range detection comprises: decoding a range detection instruction from an input vector X and a Range limit vector T, performing single instruction majority data (SIMD) range detection; and in response to the range detection instruction, performing SIMD comparison to match the range of the curve equation function to each input point element of the input vector X, and accumulating SIMD Comparing the results to produce a corresponding range vector R comprising a range of values of the curve equation function, including the corresponding input point of the input vector X, and The range vector R is stored as a result of the range detection in a SIMD register. The method of claim 9, wherein the range detection instruction causes the range detection logic to generate the range vector including the complex range value. The method of claim 10, wherein the range detection logic includes comparison logic to compare each of the complex input values with a corresponding limit range vector element. The method of claim 10, wherein the logic comprises binary search logic to compare each of the complex input values with a corresponding limit range vector element. A system for performing range detection, comprising: a memory to store execution instructions; a processor to determine a range value corresponding to each curve equation polynomial for a complex input vector element; wherein the processor comprises: decoding Logic to decode the execution instruction including a range detection instruction to perform single instruction majority data (SIMD) range detection from an input vector X and a range restriction vector T; and execution logic responsive to the range detection instruction to Performing a SIMD comparison such that the range of the curve equation polynomial matches each input vector element of the input vector X and accumulating the SIMD comparison result to produce a corresponding range vector R comprising a range of values of the curve equation polynomial, including the Enter the corresponding input vector element of vector X. The system of claim 13, wherein the processor includes comparison logic to compare each element of the input vector with a corresponding range limit vector element. The system of claim 13, wherein the processor includes binary search logic to compare each element of the input vector with a corresponding range limit vector element. The system of claim 13, wherein the processor includes a range vector storage to store the range vector including the range values. A system as in claim 16 wherein the processor includes an input vector storage for storing the input vector elements. The system of claim 17, wherein the processor includes at least one coefficient vector storage to store complex coefficient vector elements corresponding to the input vector elements. The system of claim 18, wherein the processor includes at least one offset vector storage to store complex offset vector elements corresponding to the input vector elements. A processor comprising: first logic to perform range detection to generate a complex range value corresponding to a complex input value of a curve equation function; second logic to perform a coefficient matching operation to generate a complex number corresponding to a complex polynomial a coefficient, the polynomial corresponding to an input value of the curve equation function; a third logic to perform a polynomial evaluation calculation to generate a corresponding a complex output value of the complex input value; wherein the first logic includes: decoding logic to decode an execution instruction including a range detection instruction to execute a single instruction majority data (SIMD) from an input vector X and a range restriction vector T Range detection; and execution logic responsive to the range detection instruction to perform SIMD comparison to match the range of the curve equation polynomial to each input vector element of the input vector X and to accumulate the SIMD comparison result to produce a corresponding range A vector R comprising a range of values of the polynomial of the curve equation, including the corresponding input vector element of the input vector X. The processor of claim 20, wherein the range detection instruction causes the first logic to generate the norm vector R including the complex range value, and storing the range vector R as a range in a SIMD register The result of the test instruction. The processor of claim 21, wherein the first logic comprises comparison logic to compare each of the complex input values with a corresponding range limit vector element. The processor of claim 21, wherein the first logic comprises binary search logic to compare each of the complex input values with a corresponding range limit vector element.