from:"Muthukumar, Aravindan"

Re: [Mesa-dev] [PATCH v4] i965 : optimized bucket index calculation

2017-11-19 Thread Muthukumar, Aravindan

Hi Ian,
Could you please review the below version of the patch and provide the 
comments? 
All the comments which were given in the previous versions are incorporated.

Thanks,
Aravindan

> -Original Message-
> From: Muthukumar, Aravindan
> Sent: Thursday, November 9, 2017 11:15 AM
> To: mesa-dev@lists.freedesktop.org
> Cc: Muthukumar, Aravindan <aravindan.muthuku...@intel.com>; J Karanje,
> Kedar <kedar.j.kara...@intel.com>
> Subject: [PATCH v4] i965 : optimized bucket index calculation
> 
> From: Aravindan Muthukumar <aravindan.muthuku...@intel.com>
> 
> Reducing Bucket index calculation to O(1).
> 
> This algorithm calculates the index using matrix method.
> Matrix arrangement is as below:
> Assuming PAGE_SIZE is 4096.
> 
>   1*4096   2*40963*40964*4096
>   5*4096   6*40967*40968*4096
>   10*4096  12*4096   14*4096   16*4096
>   20*4096  24*4096   28*4096   32*4096
>...  ...   ...   ...
>...  ...   ...   ...
>...  ...   ...   max_cache_size
> 
> From this matrix its clearly seen that every row follows the below way:
>   ...   ...   ...n
> n+(1/4)n  n+(1/2)n  n+(3/4)n2n
> 
> Row is calculated as log2(size/PAGE_SIZE) Column is calculated as converting
> the difference between the elements to fit into power size of two and indexing
> it.
> 
> Final Index is (row*4)+(col-1)
> 
> Tested with Intel Mesa CI.
> 
> Improves performance of 3DMark on BXT by 0.705966% +/- 0.229767% (n=20)
> 
> v4: Review comments on style and code comments implemented (Ian).
> v3: Review comments implemented (Ian).
> v2: Review comments implemented (Jason).
> 
> Signed-off-by: Aravindan Muthukumar <aravindan.muthuku...@intel.com>
> Signed-off-by: Kedar Karanje <kedar.j.kara...@intel.com>
> Reviewed-by: Yogesh Marathe <yogesh.mara...@intel.com>
> ---
>  src/mesa/drivers/dri/i965/brw_bufmgr.c | 47
> --
>  1 file changed, 39 insertions(+), 8 deletions(-)
> 
> diff --git a/src/mesa/drivers/dri/i965/brw_bufmgr.c
> b/src/mesa/drivers/dri/i965/brw_bufmgr.c
> index 17036b5..f21df5a 100644
> --- a/src/mesa/drivers/dri/i965/brw_bufmgr.c
> +++ b/src/mesa/drivers/dri/i965/brw_bufmgr.c
> @@ -86,6 +86,8 @@
> 
>  #define memclear(s) memset(, 0, sizeof(s))
> 
> +#define PAGE_SIZE 4096
> +
>  #define FILE_DEBUG_FLAG DEBUG_BUFMGR
> 
>  static inline int
> @@ -180,19 +182,44 @@ bo_tile_pitch(struct brw_bufmgr *bufmgr, uint32_t
> pitch, uint32_t tiling)
> return ALIGN(pitch, tile_width);
>  }
> 
> +/**
> + * This function finds the correct bucket fit for the input size.
> + * The function works with O(1) complexity when the requested size
> + * was queried instead of iterating the size through all the buckets.
> + */
>  static struct bo_cache_bucket *
>  bucket_for_size(struct brw_bufmgr *bufmgr, uint64_t size)  {
> -   int i;
> +   /* Calculating the pages and rounding up to the page size. */
> +   const unsigned pages = (size + PAGE_SIZE - 1) / PAGE_SIZE;
> +
> +   /* Row  Bucket sizesclz((x-1) | 3)   RowColumn
> +*in pages  stride   size
> +*   0:   1  2  3  4 -> 30 30 30 304   1
> +*   1:   5  6  7  8 -> 29 29 29 294   1
> +*   2:  10 12 14 16 -> 28 28 28 288   2
> +*   3:  20 24 28 32 -> 27 27 27 27   16   4
> +*/
> +   const unsigned row = 30 - __builtin_clz((pages - 1) | 3);
> +   const unsigned row_max_pages = 4 << row;
> +
> +   /* The '& ~2' is the special case for row 1. In row 1, max pages /
> +* 2 is 2, but the previous row maximum is zero (because there is
> +* no previous row). All row maximum sizes are power of 2, so that
> +* is the only case where that bit will be set.
> +*/
> +   const unsigned prev_row_max_pages = (row_max_pages / 2) & ~2;
> +   int col_size_log2 = row - 1;
> +   col_size_log2 += (col_size_log2 < 0);
> 
> -   for (i = 0; i < bufmgr->num_buckets; i++) {
> -  struct bo_cache_bucket *bucket = >cache_bucket[i];
> -  if (bucket->size >= size) {
> - return bucket;
> -  }
> -   }
> +   const unsigned col = (pages - prev_row_max_pages +
> +((1 << col_size_log2) - 1)) >> col_size_log2;
> 
> -   return NULL;
> +   /* Calculating the index based on the row and column. */
> +   const unsigned index = (row * 4) + (col - 1);
> +
> +   return (index < bufmgr->num_buckets) ?
> +  >cache_bucket[index] : NULL;
>  }
&g

Re: [Mesa-dev] [PATCH v3] i965 : optimized bucket index calculation

2017-11-08 Thread Muthukumar, Aravindan

> On 11/06/2017 08:30 PM, aravindan.muthuku...@intel.com wrote:
> > From: Aravindan Muthukumar 
> >
> > Now the complexity has been reduced to O(1)
> >
> > Algorithm calculates the index using matrix method.
> > Matrix arrangement is as below:
> > Assuming PAGE_SIZE is 4096.
> >
> >   1*4096   2*40963*40964*4096
> >   5*4096   6*40967*40968*4096
> >   10*4096  12*4096   14*4096   16*4096
> >   20*4096  24*4096   28*4096   32*4096
> >...  ...   ...   ...
> >...  ...   ...   ...
> >...  ...   ...   max_cache_size
> >
> > From this matrix its clearly seen that every row follows the below
> > way:
> >   ...   ...   ...n
> > n+(1/4)n  n+(1/2)n  n+(3/4)n2n
> >
> > Row is calculated as log2(size/PAGE_SIZE) Column is calculated as
> > converting the difference between the elements to fit into power size
> > of two and indexing it.
> >
> > Final Index is (row*4)+(col-1)
> >
> > Tested with Intel Mesa CI.
> >
> > Improves performance of 3DMark on BXT by 0.705966% +/- 0.229767%
> > (n=20)
> >
> > v3: review comments implemented (Ian).
> > v2: review comments implemented (Jason).
> >
> > Signed-off-by: Aravindan Muthukumar 
> > Signed-off-by: Kedar Karanje 
> > Reviewed-by: Yogesh Marathe 
> > ---
> >  src/mesa/drivers/dri/i965/brw_bufmgr.c | 38
> > +++---
> >  1 file changed, 30 insertions(+), 8 deletions(-)
> >
> > diff --git a/src/mesa/drivers/dri/i965/brw_bufmgr.c
> > b/src/mesa/drivers/dri/i965/brw_bufmgr.c
> > index 17036b5..9a423da 100644
> > --- a/src/mesa/drivers/dri/i965/brw_bufmgr.c
> > +++ b/src/mesa/drivers/dri/i965/brw_bufmgr.c
> > @@ -86,6 +86,8 @@
> >
> >  #define memclear(s) memset(, 0, sizeof(s))
> >
> > +#define PAGE_SIZE 4096
> > +
> >  #define FILE_DEBUG_FLAG DEBUG_BUFMGR
> >
> >  static inline int
> > @@ -180,19 +182,35 @@ bo_tile_pitch(struct brw_bufmgr *bufmgr, uint32_t
> pitch, uint32_t tiling)
> > return ALIGN(pitch, tile_width);
> >  }
> >
> > +/*
> > + * This function finds the correct bucket fit for the input size.
> > + * The function works with O(1) complexity when the requested size
> > + * was queried instead of iterating the size through all the buckets.
> > + */
> >  static struct bo_cache_bucket *
> >  bucket_for_size(struct brw_bufmgr *bufmgr, uint64_t size)  {
> > -   int i;
> > +   /* Calculating the pages and rounding up to the page size. */
> > +   const unsigned int pages = (size + PAGE_SIZE - 1) / PAGE_SIZE;
> >
> > -   for (i = 0; i < bufmgr->num_buckets; i++) {
> > -  struct bo_cache_bucket *bucket = >cache_bucket[i];
> > -  if (bucket->size >= size) {
> > - return bucket;
> > -  }
> > -   }
> > +   /* Finding the row number based on the calculated pages. */
> > +   const unsigned int rows = 30 - __builtin_clz((pages - 1) | 3);
> >
> > -   return NULL;
> 
> Why did you make random (and incorrect) style changes and delete
> (useful) comments from the code I sent?
>

> > > Thanks Ian. I added comments based on my understanding and I get the 
> > > point I'll push v4 with your comments.
 
> > +   const unsigned int row_max_pages = 4 << rows;
> > +   const unsigned int prev_row_max_pages = (row_max_pages / 2) & ~2;
> > +
> > +   /* Finding the column number using column interval. */
> > +   int col_size_log2 = rows - 1;
> > +   col_size_log2 += (col_size_log2 < 0);
> > +
> > +   const unsigned int col = ( (pages - prev_row_max_pages +
> > +( (1 << col_size_log2) - 1) ) >>
> > + col_size_log2 );
> > +
> > +   /* Calculating the index based on the row and column. */
> > +   const unsigned int index = (rows * 4) + (col - 1);
> > +
> > +   return (index < bufmgr->num_buckets) ?
> > +  >cache_bucket[index] : NULL;
> >  }
> >
> >  int
> > @@ -1254,6 +1272,10 @@ add_bucket(struct brw_bufmgr *bufmgr, int size)
> > list_inithead(>cache_bucket[i].head);
> > bufmgr->cache_bucket[i].size = size;
> > bufmgr->num_buckets++;
> > +
> > +   assert(bucket_for_size(bufmgr, size) == >cache_bucket[i]);
> > +   assert(bucket_for_size(bufmgr, size - 2048) == 
> > >cache_bucket[i]);
> > +   assert(bucket_for_size(bufmgr, size + 1) !=
> > + >cache_bucket[i]);
> >  }
> >
> >  static void
> >

___
mesa-dev mailing list
mesa-dev@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/mesa-dev

Re: [Mesa-dev] [PATCH v2] i965 : optimized bucket index calculation

2017-11-02 Thread Muthukumar, Aravindan

> > >On 10/24/2017 02:42 AM, Muthukumar, Aravindan wrote:
> > >>> -Original Message-
> > >>> From: Ian Romanick [mailto:i...@freedesktop.org]
> > >>> Sent: Friday, October 20, 2017 9:51 AM
> > >>> To: Muthukumar, Aravindan <aravindan.muthuku...@intel.com>; mesa-
> > >>> d...@lists.freedesktop.org
> > >>> Cc: J Karanje, Kedar <kedar.j.kara...@intel.com>; Tamminen, Eero T
> > >>> <eero.t.tammi...@intel.com>
> > >>> Subject: Re: [Mesa-dev] [PATCH v2] i965 : optimized bucket index
> > >>> calculation
> > >>>
> > >>> On 09/13/2017 11:43 PM, aravindan.muthuku...@intel.com wrote:
> > >>>> From: Aravindan Muthukumar <aravindan.muthuku...@intel.com>
> > >>>>
> > >>>> Avoiding the loop which was running with O(n) complexity.
> > >>>> Now the complexity has been reduced to O(1)
> > >>>>
> > >>>> Algorithm calculates the index using matrix method.
> > >>>> Matrix arrangement is as below:
> > >>>> Assuming PAGE_SIZE is 4096.
> > >>>>
> > >>>>  1*4096   2*40963*40964*4096
> > >>>>  5*4096   6*40967*40968*4096
> > >>>
> > >>> I think adding one more row to this chart would make it more clear.
> > >>> The two rows shown also follow a simpler pattern, and that made
> > >>> some of the complexity below seem confusing.
> > >>>
> > >>>10*4096  12*4096   14*4096   16*4096
> > >>>
> > >>>>   ...  ...   ...   ...
> > >>>>   ...  ...   ...   ...
> > >>>>   ...  ...   ...   max_cache_size
> > >>>>
> > >>>> From this matrix its cleary seen that every row
> > >>>clearly
> > >>>
> > >>>> follows the below way:
> > >>>>  ...   ...   ...n
> > >>>>n+(1/4)n  n+(1/2)n  n+(3/4)n2n
> > >>>>
> > >>>> Row is calulated as log2(size/PAGE_SIZE) Column is calculated as
> > >>>> converting the difference between the elements to fit into power
> > >>>> size of two and indexing it.
> > >>>>
> > >>>> Final Index is (row*4)+(col-1)
> > >>>>
> > >>>> Tested with Intel Mesa CI.
> > >>>>
> > >>>> Improves performance of 3d Mark on Broxton.
> > >>>> Analyzed using Compare Perf Analyser:
> > >>>> Average : 201.2 +/- 65.4836 (n=20)
> > >>>
> > >>> Is 201 the improvement or the absolute score?  Do not quote
> > >>> absolute
> > scores.
> > >>>
> > >>>> Percentage : 0.705966% +/- 0.229767% (n=20)
> > >>>
> > >>> Eero: Can you reproduce this result on BXT or other platforms?
> > >>> Just
> > curious...
> > >>>
> > >>>> v2: Review comments regarding cosmetics and asserts implemented
> > >>>>
> > >>>> Signed-off-by: Aravindan Muthukumar
> > >>>> <aravindan.muthuku...@intel.com>
> > >>>> Signed-off-by: Kedar Karanje <kedar.j.kara...@intel.com>
> > >>>> Reviewed-by: Yogesh Marathe <yogesh.mara...@intel.com>
> > >>>> ---
> > >>>>  src/mesa/drivers/dri/i965/brw_bufmgr.c | 46
> > >>>> --
> > >>>>  1 file changed, 39 insertions(+), 7 deletions(-)
> > >>>>
> > >>>> diff --git a/src/mesa/drivers/dri/i965/brw_bufmgr.c
> > >>>> b/src/mesa/drivers/dri/i965/brw_bufmgr.c
> > >>>> index 8017219..8013ccb 100644
> > >>>> --- a/src/mesa/drivers/dri/i965/brw_bufmgr.c
> > >>>> +++ b/src/mesa/drivers/dri/i965/brw_bufmgr.c
> > >>>> @@ -87,6 +87,8 @@
> > >>>>
> > >>>>  #define memclear(s) memset(, 0, sizeof(s))
> > >>>>
> > >>>> +#define PAGE_SIZE 4096
> > >>>> +
> > >>>>  #define FILE_DEBUG_FLAG DEBUG_BUFMGR
> > >>>>
> > >>>>  static inline int
> > >>>> @@ -181,19 +183,45 @@ bo_tile

Re: [Mesa-dev] [PATCH v2] i965 : optimized bucket index calculation

2017-10-24 Thread Muthukumar, Aravindan

> -Original Message-
> From: Ian Romanick [mailto:i...@freedesktop.org]
> Sent: Friday, October 20, 2017 9:51 AM
> To: Muthukumar, Aravindan <aravindan.muthuku...@intel.com>; mesa-
> d...@lists.freedesktop.org
> Cc: J Karanje, Kedar <kedar.j.kara...@intel.com>; Tamminen, Eero T
> <eero.t.tammi...@intel.com>
> Subject: Re: [Mesa-dev] [PATCH v2] i965 : optimized bucket index calculation
> 
> On 09/13/2017 11:43 PM, aravindan.muthuku...@intel.com wrote:
> > From: Aravindan Muthukumar <aravindan.muthuku...@intel.com>
> >
> > Avoiding the loop which was running with O(n) complexity.
> > Now the complexity has been reduced to O(1)
> >
> > Algorithm calculates the index using matrix method.
> > Matrix arrangement is as below:
> > Assuming PAGE_SIZE is 4096.
> >
> >  1*4096   2*40963*40964*4096
> >  5*4096   6*40967*40968*4096
> 
> I think adding one more row to this chart would make it more clear.  The two
> rows shown also follow a simpler pattern, and that made some of the
> complexity below seem confusing.
> 
>10*4096  12*4096   14*4096   16*4096
> 
> >   ...  ...   ...   ...
> >   ...  ...   ...   ...
> >   ...  ...   ...   max_cache_size
> >
> > From this matrix its cleary seen that every row
>clearly
> 
> > follows the below way:
> >  ...   ...   ...n
> >n+(1/4)n  n+(1/2)n  n+(3/4)n2n
> >
> > Row is calulated as log2(size/PAGE_SIZE) Column is calculated as
> > converting the difference between the elements to fit into power size
> > of two and indexing it.
> >
> > Final Index is (row*4)+(col-1)
> >
> > Tested with Intel Mesa CI.
> >
> > Improves performance of 3d Mark on Broxton.
> > Analyzed using Compare Perf Analyser:
> > Average : 201.2 +/- 65.4836 (n=20)
> 
> Is 201 the improvement or the absolute score?  Do not quote absolute scores.
> 
> > Percentage : 0.705966% +/- 0.229767% (n=20)
> 
> Eero: Can you reproduce this result on BXT or other platforms?  Just 
> curious...
> 
> > v2: Review comments regarding cosmetics and asserts implemented
> >
> > Signed-off-by: Aravindan Muthukumar <aravindan.muthuku...@intel.com>
> > Signed-off-by: Kedar Karanje <kedar.j.kara...@intel.com>
> > Reviewed-by: Yogesh Marathe <yogesh.mara...@intel.com>
> > ---
> >  src/mesa/drivers/dri/i965/brw_bufmgr.c | 46
> > --
> >  1 file changed, 39 insertions(+), 7 deletions(-)
> >
> > diff --git a/src/mesa/drivers/dri/i965/brw_bufmgr.c
> > b/src/mesa/drivers/dri/i965/brw_bufmgr.c
> > index 8017219..8013ccb 100644
> > --- a/src/mesa/drivers/dri/i965/brw_bufmgr.c
> > +++ b/src/mesa/drivers/dri/i965/brw_bufmgr.c
> > @@ -87,6 +87,8 @@
> >
> >  #define memclear(s) memset(, 0, sizeof(s))
> >
> > +#define PAGE_SIZE 4096
> > +
> >  #define FILE_DEBUG_FLAG DEBUG_BUFMGR
> >
> >  static inline int
> > @@ -181,19 +183,45 @@ bo_tile_pitch(struct brw_bufmgr *bufmgr, uint32_t
> pitch, uint32_t tiling)
> > return ALIGN(pitch, tile_width);
> >  }
> >
> > +static inline int
> > +ilog2_round_up(int value)
> > +{
> > +   assert(value != 0);
> > +   return 32 - __builtin_clz(value - 1); }
> > +
> > +/*
> > + * This function finds the correct bucket fit for the input size.
> > + * The function works with O(1) complexity when the requested size
> > + * was queried instead of iterating the size through all the buckets.
> > + */
> >  static struct bo_cache_bucket *
> >  bucket_for_size(struct brw_bufmgr *bufmgr, uint64_t size)  {
> > -   int i;
> > +   int index = -1;
> 
> I don't see how execution could get to that test without index being set 
> again,
> so it should be safe to remove the initialization.
> 

We will skip this initialization since it doesn’t impact the index result.

  
> > +   int row, col = 0;
> > +   int pages, pages_log2;
> 
> Move the declarations of row, col, pages, and pages_log2 into the else case,
> initialize them with the only assignment to them, and make them const.
> 
> Since all of these values, including index, get values derived from size, I 
> believe
> the should all be unsigned.  In that case, remove the index >= 0 test below.
> 

We will move as well as initialize the above variables in the respective else 
part. 

> >
> > -   for (i = 0; i < bufmgr->num_buckets; i++) {
&

Re: [Mesa-dev] [PATCH v2] i965 : optimized bucket index calculation

2017-10-16 Thread Muthukumar, Aravindan

Hi Jason,
Please review and let us know if any other changes need to be done for 
this patch.
We have incorporated all the review comments in the second version of the patch.

Thanks,
Aravindan

> -Original Message-
> From: Muthukumar, Aravindan
> Sent: Tuesday, October 3, 2017 10:04 AM
> To: Marathe, Yogesh <yogesh.mara...@intel.com>; Ekstrand, Jason
> <jason.ekstr...@intel.com>; Palli, Tapani <tapani.pa...@intel.com>; Ian
> Romanick <i...@freedesktop.org>; Emil Velikov <emil.l.veli...@gmail.com>
> Cc: J Karanje, Kedar <kedar.j.kara...@intel.com>; mesa-
> d...@lists.freedesktop.org
> Subject: RE: [Mesa-dev] [PATCH v2] i965 : optimized bucket index calculation
> 
> Hi Reviewers,
>   Please review and provide the comments on the second version of the
> patch.
> 
> Thanks,
> Aravindan
> 
> > -Original Message-
> > From: Marathe, Yogesh
> > Sent: Friday, September 22, 2017 8:41 AM
> > To: Ekstrand, Jason <jason.ekstr...@intel.com>; Palli, Tapani
> > <tapani.pa...@intel.com>; Ian Romanick <i...@freedesktop.org>; Emil
> > Velikov <emil.l.veli...@gmail.com>
> > Cc: Muthukumar, Aravindan <aravindan.muthuku...@intel.com>; J Karanje,
> > Kedar <kedar.j.kara...@intel.com>; mesa-dev@lists.freedesktop.org
> > Subject: RE: [Mesa-dev] [PATCH v2] i965 : optimized bucket index
> > calculation
> >
> > + all v1 reviewers. Does this look ok?
> >
> > -Yogesh.
> >
> > >-Original Message-
> > >From: mesa-dev [mailto:mesa-dev-boun...@lists.freedesktop.org] On
> > >Behalf Of aravindan.muthuku...@intel.com
> > >Sent: Thursday, September 14, 2017 12:13 PM
> > >To: mesa-dev@lists.freedesktop.org
> > >Cc: Muthukumar, Aravindan <aravindan.muthuku...@intel.com>; J
> > >Karanje, Kedar <kedar.j.kara...@intel.com>
> > >Subject: [Mesa-dev] [PATCH v2] i965 : optimized bucket index
> > >calculation
> > >
> > >From: Aravindan Muthukumar <aravindan.muthuku...@intel.com>
> > >
> > >Avoiding the loop which was running with O(n) complexity.
> > >Now the complexity has been reduced to O(1)
> > >
> > >Algorithm calculates the index using matrix method.
> > >Matrix arrangement is as below:
> > >Assuming PAGE_SIZE is 4096.
> > >
> > > 1*4096   2*40963*40964*4096
> > > 5*4096   6*40967*40968*4096
> > >  ...  ...   ...   ...
> > >  ...  ...   ...   ...
> > >  ...  ...   ...   max_cache_size
> > >
> > >From this matrix its cleary seen that every row follows the below way:
> > > ...   ...   ...n
> > >   n+(1/4)n  n+(1/2)n  n+(3/4)n2n
> > >
> > >Row is calulated as log2(size/PAGE_SIZE) Column is calculated as
> > >converting the difference between the elements to fit into power size
> > >of two
> > and indexing it.
> > >
> > >Final Index is (row*4)+(col-1)
> > >
> > >Tested with Intel Mesa CI.
> > >
> > >Improves performance of 3d Mark on Broxton.
> > >Analyzed using Compare Perf Analyser:
> > >Average : 201.2 +/- 65.4836 (n=20)
> > >Percentage : 0.705966% +/- 0.229767% (n=20)
> > >
> > >v2: Review comments regarding cosmetics and asserts implemented
> > >
> > >Signed-off-by: Aravindan Muthukumar <aravindan.muthuku...@intel.com>
> > >Signed-off-by: Kedar Karanje <kedar.j.kara...@intel.com>
> > >Reviewed-by: Yogesh Marathe <yogesh.mara...@intel.com>
> > >---
> > > src/mesa/drivers/dri/i965/brw_bufmgr.c | 46
> > >--
> > > 1 file changed, 39 insertions(+), 7 deletions(-)
> > >
> > >diff --git a/src/mesa/drivers/dri/i965/brw_bufmgr.c
> > >b/src/mesa/drivers/dri/i965/brw_bufmgr.c
> > >index 8017219..8013ccb 100644
> > >--- a/src/mesa/drivers/dri/i965/brw_bufmgr.c
> > >+++ b/src/mesa/drivers/dri/i965/brw_bufmgr.c
> > >@@ -87,6 +87,8 @@
> > >
> > > #define memclear(s) memset(, 0, sizeof(s))
> > >
> > >+#define PAGE_SIZE 4096
> > >+
> > > #define FILE_DEBUG_FLAG DEBUG_BUFMGR
> > >
> > > static inline int
> > >@@ -181,19 +183,45 @@ bo_tile_pitch(struct brw_bufmgr *bufmgr,
> > >uint32_t pitch, uint32_t tiling)
> > >return ALIGN(pitch, tile_width);
> > > }
> > >
> > >+static inline

Re: [Mesa-dev] [PATCH v2] i965 : optimized bucket index calculation

2017-10-02 Thread Muthukumar, Aravindan

Hi Reviewers,
Please review and provide the comments on the second version of the 
patch.

Thanks,
Aravindan

> -Original Message-
> From: Marathe, Yogesh
> Sent: Friday, September 22, 2017 8:41 AM
> To: Ekstrand, Jason <jason.ekstr...@intel.com>; Palli, Tapani
> <tapani.pa...@intel.com>; Ian Romanick <i...@freedesktop.org>; Emil Velikov
> <emil.l.veli...@gmail.com>
> Cc: Muthukumar, Aravindan <aravindan.muthuku...@intel.com>; J Karanje,
> Kedar <kedar.j.kara...@intel.com>; mesa-dev@lists.freedesktop.org
> Subject: RE: [Mesa-dev] [PATCH v2] i965 : optimized bucket index calculation
> 
> + all v1 reviewers. Does this look ok?
> 
> -Yogesh.
> 
> >-Original Message-
> >From: mesa-dev [mailto:mesa-dev-boun...@lists.freedesktop.org] On
> >Behalf Of aravindan.muthuku...@intel.com
> >Sent: Thursday, September 14, 2017 12:13 PM
> >To: mesa-dev@lists.freedesktop.org
> >Cc: Muthukumar, Aravindan <aravindan.muthuku...@intel.com>; J Karanje,
> >Kedar <kedar.j.kara...@intel.com>
> >Subject: [Mesa-dev] [PATCH v2] i965 : optimized bucket index
> >calculation
> >
> >From: Aravindan Muthukumar <aravindan.muthuku...@intel.com>
> >
> >Avoiding the loop which was running with O(n) complexity.
> >Now the complexity has been reduced to O(1)
> >
> >Algorithm calculates the index using matrix method.
> >Matrix arrangement is as below:
> >Assuming PAGE_SIZE is 4096.
> >
> > 1*4096   2*40963*40964*4096
> > 5*4096   6*40967*40968*4096
> >  ...  ...   ...   ...
> >  ...  ...   ...   ...
> >  ...  ...   ...   max_cache_size
> >
> >From this matrix its cleary seen that every row follows the below way:
> > ...   ...   ...n
> >   n+(1/4)n  n+(1/2)n  n+(3/4)n2n
> >
> >Row is calulated as log2(size/PAGE_SIZE) Column is calculated as
> >converting the difference between the elements to fit into power size of two
> and indexing it.
> >
> >Final Index is (row*4)+(col-1)
> >
> >Tested with Intel Mesa CI.
> >
> >Improves performance of 3d Mark on Broxton.
> >Analyzed using Compare Perf Analyser:
> >Average : 201.2 +/- 65.4836 (n=20)
> >Percentage : 0.705966% +/- 0.229767% (n=20)
> >
> >v2: Review comments regarding cosmetics and asserts implemented
> >
> >Signed-off-by: Aravindan Muthukumar <aravindan.muthuku...@intel.com>
> >Signed-off-by: Kedar Karanje <kedar.j.kara...@intel.com>
> >Reviewed-by: Yogesh Marathe <yogesh.mara...@intel.com>
> >---
> > src/mesa/drivers/dri/i965/brw_bufmgr.c | 46
> >--
> > 1 file changed, 39 insertions(+), 7 deletions(-)
> >
> >diff --git a/src/mesa/drivers/dri/i965/brw_bufmgr.c
> >b/src/mesa/drivers/dri/i965/brw_bufmgr.c
> >index 8017219..8013ccb 100644
> >--- a/src/mesa/drivers/dri/i965/brw_bufmgr.c
> >+++ b/src/mesa/drivers/dri/i965/brw_bufmgr.c
> >@@ -87,6 +87,8 @@
> >
> > #define memclear(s) memset(, 0, sizeof(s))
> >
> >+#define PAGE_SIZE 4096
> >+
> > #define FILE_DEBUG_FLAG DEBUG_BUFMGR
> >
> > static inline int
> >@@ -181,19 +183,45 @@ bo_tile_pitch(struct brw_bufmgr *bufmgr, uint32_t
> >pitch, uint32_t tiling)
> >return ALIGN(pitch, tile_width);
> > }
> >
> >+static inline int
> >+ilog2_round_up(int value)
> >+{
> >+   assert(value != 0);
> >+   return 32 - __builtin_clz(value - 1); }
> >+
> >+/*
> >+ * This function finds the correct bucket fit for the input size.
> >+ * The function works with O(1) complexity when the requested size
> >+ * was queried instead of iterating the size through all the buckets.
> >+ */
> > static struct bo_cache_bucket *
> > bucket_for_size(struct brw_bufmgr *bufmgr, uint64_t size)  {
> >-   int i;
> >+   int index = -1;
> >+   int row, col = 0;
> >+   int pages, pages_log2;
> >
> >-   for (i = 0; i < bufmgr->num_buckets; i++) {
> >-  struct bo_cache_bucket *bucket = >cache_bucket[i];
> >-  if (bucket->size >= size) {
> >- return bucket;
> >-  }
> >+   /* condition for size less  than 4*4096 (16KB) page size */
> >+   if(size <= 4 * PAGE_SIZE) {
> >+  index = DIV_ROUND_UP(size, PAGE_SIZE) - 1;;
> >+   } else {
> >+  /* Number of pages of page size */
> >+  pages = DIV_ROUND_UP(size, PAGE_SIZE);
> >+  pages_log2 = ilog2_round_up(page

Re: [Mesa-dev] [PATCH] i965: Avoids loop for buffer object availability in add_exec_bo

2017-08-04 Thread Muthukumar, Aravindan

Hi Chris,

> -Original Message-
> From: Chris Wilson [mailto:ch...@chris-wilson.co.uk]
> Sent: Tuesday, August 1, 2017 2:35 PM
> To: Marathe, Yogesh <yogesh.mara...@intel.com>; mesa-
> d...@lists.freedesktop.org
> Cc: Muthukumar, Aravindan <aravindan.muthuku...@intel.com>
> Subject: RE: [Mesa-dev] [PATCH] i965: Avoids loop for buffer object 
> availability
> in add_exec_bo
> 
> Quoting Marathe, Yogesh (2017-08-01 09:21:51)
> > > > -Original Message-
> > > > From: Chris Wilson [mailto:ch...@chris-wilson.co.uk]
> > > > Sent: Friday, July 28, 2017 2:30 PM
> > > > To: Muthukumar, Aravindan <aravindan.muthuku...@intel.com>; mesa-
> > > > d...@lists.freedesktop.org
> > > > Cc: Marathe, Yogesh <yogesh.mara...@intel.com>; Muthukumar,
> > > > Aravindan <aravindan.muthuku...@intel.com>
> > > > Subject: Re: [Mesa-dev] [PATCH] i965: Avoids loop for buffer
> > > > object availability in add_exec_bo
> > > >
> > > > Quoting aravindan.muthuku...@intel.com (2017-07-28 09:37:01)
> > > > > From: Aravindan Muthukumar <aravindan.muthuku...@intel.com>
> > > > >
> > > > > Original logic loops over the list for every buffer object.
> > > > > Maintained a flag to identify whether bo is already there in list.
> > > >
> > > > No. brw_bo is shared between many contexts, and so you are marking
> > > > it as available in every one. May I suggest looking for issues in
> > > > https://patchwork.freedesktop.org/series/27719/ and help bring
> > > > that series to fruition.
> > >
> > > Thanks Chris, we'll get back.
> >
> > Agreed. The patch series you have pointed out covers it, patch can be
> dropped.
> > We tried applying series on master but it didn't apply cleanly, is
> > there a base commit/branch on which this was tested / expected to work?
> 
> The tip of https://cgit.freedesktop.org/~ickle/mesa/log/?h=qbo
> i.e.
> https://cgit.freedesktop.org/~ickle/mesa/commit/?h=qbo=b40fa6633bdac9
> 4cef2fd5f56360dfdb5eeb3738

I tested the patch series with mesa demos which seems functionally fine. 
Is there any specific functional/perf issue that needs to be looked at?

> -Chris
___
mesa-dev mailing list
mesa-dev@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/mesa-dev

Re: [Mesa-dev] [PATCH v4] i965 : optimized bucket index calculation

Re: [Mesa-dev] [PATCH v3] i965 : optimized bucket index calculation

Re: [Mesa-dev] [PATCH v2] i965 : optimized bucket index calculation

Re: [Mesa-dev] [PATCH v2] i965 : optimized bucket index calculation

Re: [Mesa-dev] [PATCH v2] i965 : optimized bucket index calculation

Re: [Mesa-dev] [PATCH v2] i965 : optimized bucket index calculation

Re: [Mesa-dev] [PATCH] i965: Avoids loop for buffer object availability in add_exec_bo

7 matches

Site Navigation

Mail list logo

Footer information