Performing scrambling and/or descrambling on parallel computing architectures

Abstract

Apparatuses, systems, and techniques to descramble or scramble data use a graphics processing unit (GPU) to perform descrambling. For example, in at least one embodiment, generation of a descrambling sequence is distributed among GPU threads for parallel calculation of the descrambling sequence and/or descrambling is distributed among GPU threads for descrambling.

What is claimed is: 
     
         1 . A method, comprising:
 obtaining an input data sequence comprising a plurality of input data values, each having a value and a position in the input data sequence;   obtaining a descrambling sequence comprising a plurality of descrambling values with positions corresponding to positions of input data values in the input data sequence;   allocating the input data sequence to threads of a plurality of threads of a graphics processing unit (GPU);   allocating the descrambling sequence to threads of the plurality of threads of the GPU;   performing a descrambling operation over the input data sequence and the descrambling sequence using the threads of the plurality of threads of the GPU; and   outputting a descrambled data output of the descrambling operation.   
     
     
         2 . The method of  claim 1 , wherein the descrambling sequence is a pseudorandom bit sequence that is a function of a user identifier of a user device having transmitted the input data sequence and of a base station identifier of a base station having received the input data sequence. 
     
     
         3 . The method of  claim 2 , further comprising:
 storing the descrambling sequence as a stored descrambling sequence in a shared memory of the GPU in association with a sequence user identifier and a sequence base station identifier;   determining the user identifier and the base station identifier for a subsequent input data sequence;   determining if the user identifier is equal to the sequence user identifier;   determining if the base station identifier is equal to the sequence base station identifier; and   if the user identifier is equal to the sequence user identifier and the base station identifier is equal to the sequence base station identifier, using the stored descrambling sequence for descrambling the subsequent input data sequence.   
     
     
         4 . The method of  claim 1 , further comprising:
 storing the descrambling sequence in a shared memory of the GPU;   determining a size in bits of the descrambling sequence;   determining a data width of the threads;   determining a number of allocated threads allocated to descrambling based on the size in bits of the descrambling sequence and the data width of the threads, the number of allocated threads being sufficient to descramble in parallel at least as many input data values as the size in bits of the descrambling sequence; and   configuring the number of allocated threads to execute instructions common to the number of allocated threads, comprising a first instruction for reading into thread local memory an array of input data values, a second instruction for reading a descrambling segment from the shared memory, and a third instruction for descrambling the array of input data values using the descrambling segment.   
     
     
         5 . The method of  claim 1 , further comprising:
 storing the descrambling sequence in a shared memory of the GPU;   determining a size in bits of the descrambling sequence;   determining a data width of the threads;   determining a number of allocated threads of a plurality of blocks of threads allocated to descrambling based on the size in bits of the descrambling sequence and the data width of the threads, the number of allocated threads being sufficient to descramble in parallel at least as many input data values as the size in bits of the descrambling sequence;   reading into thread local memory an array of input data values;   reading a descrambling segment from the shared memory; and   descrambling the array of input data values using the descrambling segment.   
     
     
         6 . The method of  claim 1 , wherein the GPU is an element of a cellular network base station. 
     
     
         7 . The method of  claim 1 , further comprising:
 obtaining an initialization value for a first cycling process from a first generator polynomial for generating the descrambling sequence, wherein cycles of the first cycling process generate the descrambling sequence and the first generator polynomial corresponds to a many-to-one linear feedback shift register (LFSR) with a first feedback pattern in which a plurality of register values are feedback to a single input of the many-to-one LFSR;   determining a second cycling process represented by a one-to-many LFSR, converting from the first feedback pattern to a second feedback pattern, represented by a second generator polynomial, in which a single input of the one-to-many LFSR is fed back to a plurality of stages of the one-to-many LFSR according to the second generator polynomial;   initializing the plurality of threads of the GPU to process at least a portion of the second cycling process;   initializing a first thread of the plurality of threads to operate a first thread LFSR, wherein the first thread LFSR is initialized to a first position in the descrambling sequence with polynomial multiplication modulo the second generator polynomial and a first monomial with a first degree corresponding to the first position;   initializing a second thread of the plurality of threads to operate a second thread LFSR, wherein the second thread LFSR is initialized to a second position in the descrambling sequence with polynomial multiplication modulo the second generator polynomial and a second monomial with a second degree corresponding to the second position, wherein the first position and the second position are distinct; and   storing a first output of the first thread and a second output of the second thread as at least a portion of the descrambling sequence in a shared memory of the GPU.   
     
     
         8 . A method, comprising:
 configuring a first sequence LFSR to output a first stream of sequence LFSR output values according to a first generator polynomial for the first sequence LFSR and a first sequence LFSR initial state;   initializing a plurality of threads of a graphics processing unit (GPU) with corresponding thread LFSR initial states, wherein a thread LFSR with a corresponding thread LFSR initial state of a given thread of the plurality of threads corresponds to a predetermined number of cycle advancements of the first sequence LFSR;   cycling the thread LFSR to output a stream of thread LFSR output values; and   combining streams of thread LFSR output values over the plurality of threads, to form a descrambling sequence.   
     
     
         9 . The method of  claim 8 , wherein the first sequence LFSR corresponds to a many-to-one LFSR with a first feedback pattern in which a plurality of register values are feedback to a single input of the many-to-one LFSR, the method further comprising:
 converting from the first feedback pattern to a second feedback pattern in which a single input of a one-to-many LFSR is fed back to a plurality of register values of the one-to-many LFSR according to the first generator polynomial;   determining a predetermined number of cycle advancements of the one-to-many LFSR based on a thread position of the given thread among the plurality of threads;   initializing the given thread with the corresponding thread LFSR initial state by polynomial multiplication modulo the first generator polynomial of an initial state of the sequence LFSR and a monomial with a degree corresponding to the thread position;   advancing the thread LFSR to a state in which the thread LFSR outputs streams corresponding to the first feedback pattern; and   cycling the thread LFSR to output the stream of thread LFSR output values.   
     
     
         10 . The method of  claim 9 , further comprising:
 determining a segment monomial value of the monomial modulo the first generator polynomial; and   storing the segment monomial value in association with an associated thread, wherein the associated thread is associated with performing computation of an associated segment using the segment monomial value multiplied by the initial state of the sequence LFSR modulo the first generator polynomial as the thread LFSR initial state.   
     
     
         11 . The method of  claim 8 , further comprising:
 configuring a first sequence linear feedback shift register (LFSR) to output the first stream of sequence LFSR output values according to the first generator polynomial for the first sequence LFSR and the first sequence LFSR initial state, wherein the first sequence LFSR initial state is based on a seed value determined at least from a user identifier of a user sending an input data sequence;   configuring a second sequence linear feedback shift register (LFSR) to output a second stream of sequence LFSR output values according to a second generator polynomial for the second sequence LFSR and a second sequence LFSR initial state, wherein the second sequence LFSR initial state is based on a constant value;   initializing a first thread of the plurality of threads of the GPU to execute cycling of a first thread LFSR corresponding to the first sequence LFSR, wherein the first thread LFSR is initialized with a first thread LFSR initial state corresponding to a predetermined number of cycle advancements of the first sequence LFSR, and to execute cycling of a second thread LFSR corresponding to the second sequence LFSR, wherein the second thread LFSR is initialized with a second thread LFSR initial state corresponding to advancement of the second sequence LFSR by the predetermined number of cycle advancements;   cycling the first thread LFSR to output a first stream of thread LFSR output values;   cycling the second thread LFSR to output a second stream of thread LFSR output values; and   combining the first stream of thread LFSR output values and the second stream of thread LFSR output values as a descrambling segment output by the thread.   
     
     
         12 . The method of  claim 11 , further comprising:
 determining the predetermined number of cycle advancements of the first thread LFSR and of the second thread LFSR as a thread position of the thread multiplied by a data width of the thread;   performing cycle advancement of the first thread LFSR by polynomial multiplication modulo the first generator polynomial of the first sequence LFSR initial state and a monomial with a degree corresponding to the predetermined number of cycle advancements; and   performing cycle advancement of the second thread LFSR by polynomial multiplication modulo the second generator polynomial of the second sequence LFSR initial state and the monomial.   
     
     
         13 . The method of  claim 12 , further comprising:
 performing cycle advancement for LFSRs of the plurality of threads the GPU in parallel, wherein each descrambling segment of the descrambling sequence is output by at least one thread of the plurality of threads.   
     
     
         14 . A descrambler, for descrambling an input data sequence, comprising:
 a plurality of thread hardware units of a graphics processing unit (GPU);   a shared memory of the GPU accessible to the plurality of thread hardware units;   a shared memory area of the shared memory storing a descrambling sequence as an array of descrambling segments;   a first thread hardware unit of the plurality of thread hardware units comprising:
 1) a first execution core; 
 2) a first local memory for storage of a first input data segment as a first array of input data values, wherein the first input data segment is a first portion of the input data sequence; and 
 3) a first interface to access a first descrambling segment in a first array location of the shared memory area; 
   a second thread hardware unit of the plurality of thread hardware units comprising:
 1) a second execution core, capable of executing in parallel with the first execution core; 
 2) a second local memory for storage of a second input data segment as a second array of input data values, wherein the second input data segment is a second portion of the input data sequence; and 
 3) a second interface to access a second descrambling segment in a second array location of the shared memory area; and 
   an output for outputting a descrambled input data sequence from at least the first input data segment processed with the first descrambling segment and the second input data segment processed with the second descrambling segment.   
     
     
         15 . The descrambler of  claim 14 , wherein the descrambling sequence is 1024 bits, the plurality of thread hardware units comprises 32 thread hardware units, and descrambling segments are 32 bits wide, and wherein the first array location and the second array location are word-length memory locations in the shared memory. 
     
     
         16 . The descrambler of  claim 14 , wherein the descrambling sequence is a pseudorandom bit sequence that is a function of a user identifier of a user device having transmitted the input data sequence and of a base station identifier of a base station having received the input data sequence. 
     
     
         17 . The descrambler of  claim 14 , further comprising:
 a global memory of the GPU accessible to the first thread hardware unit and the second thread hardware unit; and   a sequence identifier storage of the global memory storing a sequence user identifier and a sequence base station identifier associated with the array of descrambling segments, usable to match a user identifier of a subsequent input data sequence with the sequence user identifier and a base station identifier of the subsequent input data sequence with the sequence base station identifier, wherein if the user identifier is equal to the sequence user identifier and the base station identifier is equal to the sequence base station identifier, the array of descrambling segments is provided for descrambling the subsequent input data sequence.   
     
     
         18 . The descrambler of  claim 14 , wherein allocated threads allocated to descrambling are configured to allocate threads to execute instructions common to the allocated threads, comprising a first instruction for reading into thread local memory an array of input data values, a second instruction for reading a descrambling segment from the shared memory, and a third instruction for descrambling the array of input data values using the descrambling segment. 
     
     
         19 . The descrambler of  claim 14 , wherein allocated threads allocated to descrambling are configured based on a size in bits of the descrambling sequence, a data width of the allocated threads, a number of allocated threads being sufficient to generate in parallel the bits of the descrambling sequence. 
     
     
         20 . A software-defined radio for communications in a mobile device communications system, comprising:
 a graphics processing unit comprising a plurality of thread hardware units comprising:
 a) a first thread hardware unit comprising a first execution core, a first instruction cache, a first local memory, and a first load/store unit coupled to a shared memory shared among threads of the plurality of thread hardware units and coupled to a global memory of the graphics processing unit; 
 b) a second thread hardware unit comprising a second execution core capable of operating in parallel with the first thread hardware unit, a second instruction cache, a second local memory, and a second load/store unit coupled to the shared memory shared and coupled to the global memory; and 
 c) a third thread hardware unit for computing a portion of a descrambling sequence, 
   wherein the first instruction cache comprises a first set of instructions for:
 1) obtaining a first input data array, wherein the first input data array is a first portion of an input data sequence received by the software-defined radio; 
 2) obtaining a first descrambling segment, wherein the first descrambling segment is a first portion of the descrambling sequence; and 
 3) performing a first descrambling operation on input data values of a first input data segment and the first descrambling segment to form a first thread output. 
   
     
     
         21 . The software-defined radio of  claim 20 , wherein the second instruction cache comprises a second set of instructions for:
 1) obtaining a second input data array, wherein the second input data array is a second portion of the input data sequence received by the software-defined radio;   2) obtaining a second descrambling segment, wherein the second descrambling segment is a second portion of the descrambling sequence; and   3) performing a second descrambling operation on input data values of a second input data segment and the second descrambling segment to form a second thread output.   
     
     
         22 . The software-defined radio of  claim 20 , wherein the descrambling sequence is a function of a plurality of LFSR outputs, wherein each LFSR of the plurality of LFSRs is a one-to-many LFSR. 
     
     
         23 . The software-defined radio of  claim 20 , further comprising:
 a second storage in the global memory for storage of a segment monomial value of a monomial modulo a generator polynomial, wherein the segment monomial value is stored in association with an associated thread, wherein the associated thread is associated with performing computation of an associated segment using the segment monomial value multiplied by an initial state of a sequence LFSR modulo the generator polynomial as a thread LFSR initial state.   
     
     
         24 . The software-defined radio of  claim 20 , further comprising:
 a second storage in the global memory for a lookup table, wherein the lookup table comprises a first set of precomputed entries for the first thread hardware unit having a first thread position, and wherein the first set of precomputed entries comprises values of polynomial multiplication of possible values of input data segments and a first generator segment associated with the first thread position.   
     
     
         25 . The software-defined radio of  claim 20 , wherein the descrambling sequence is a pseudorandom bit sequence that is a function of a user identifier of a user device having transmitted the input data sequence and of a base station identifier of a base station having received the input data sequence. 
     
     
         26 . A descrambler, for generating a descrambling sequence using a graphics processing unit (GPU), comprising:
 a plurality of thread hardware units of the GPU, comprising at least a first thread hardware unit and a second thread hardware unit;   a shared memory of the GPU accessible to the first thread hardware unit and the second thread hardware unit;   a shared memory area of the shared memory for storing the descrambling sequence as an array of descrambling segments;   the first thread hardware unit comprising:
 1) a first execution core for executing at least a first thread linear feedback shift register (LFSR); 
 2) a first local memory for storage of a first thread LFSR state, initialized to a first position in the descrambling sequence with polynomial multiplication modulo a generator polynomial and a first monomial with a first degree corresponding to the first position; and 
 3) a first interface for storing a first descrambling segment in a first array location of the shared memory area, wherein the first descrambling segment is a first output stream from the first thread LFSR initialized at the first position; and 
   the second thread hardware unit comprising:
 1) a second execution core, capable of executing in parallel with the first execution core for executing at least a second thread LFSR; 
 2) a second local memory for storage of a second thread LFSR state, initialized to a second position in the descrambling sequence with polynomial multiplication modulo the generator polynomial and a second monomial with a second degree corresponding to the second position; and 
 3) a second interface for storing a second descrambling segment in a second array location of the shared memory area, wherein the second descrambling segment is a second output stream from the second thread LFSR initialized at the second position. 
   
     
     
         27 . The descrambler of  claim 26 , wherein the descrambling sequence is 1024 bits, the first descrambling segment is 32 bits, the second descrambling segment is 32 bits, and wherein 32 thread hardware units are operated in parallel. 
     
     
         28 . The descrambler of  claim 26 , wherein the descrambling sequence is 1024 bits, wherein 32 thread hardware units are operated in parallel as a block, each operating using an instruction set common among the 32 thread hardware units. 
     
     
         29 . The descrambler of  claim 26 , wherein the descrambling sequence is a pseudorandom bit sequence that is a function of a user identifier of a user device having transmitted an input data sequence to be descrambled and of a base station identifier of a base station having received the input data sequence. 
     
     
         30 . The descrambler of  claim 26 , further comprising:
 a global memory of the GPU accessible to the first thread hardware unit and the second thread hardware unit; and   a sequence identifier storage of the global memory storing a sequence user identifier and a sequence base station identifier associated with the array of descrambling segments, usable to match a user identifier of a subsequent input data sequence with the sequence user identifier and a base station identifier of the subsequent input data sequence with the sequence base station identifier, wherein if the user identifier is equal to the sequence user identifier and the base station identifier is equal to the sequence base station identifier, the array of descrambling segments is provided for descrambling the subsequent input data sequence.   
     
     
         31 . The descrambler of  claim 26 , wherein the plurality of thread hardware units of the GPU comprise elements of a cellular network base station.