kerncraft/models/layer_condition.py
def calculate_cache_access(self):
        """Apply layer condition model to calculate cache accesses."""
        # FIXME handle multiple datatypes
        element_size = self.kernel.datatypes_size[self.kernel.datatype]

        results = {'dimensions': {}}

        def sympy_compare(a, b):
            c = 0
            for i in range(min(len(a), len(b))):
                s = a[i] - b[i]
                if sympy.simplify(s > 0):
                    c = -1
                elif sympy.simplify(s == 0):
                    c = 0
                else:
                    c = 1
                if c != 0:
                    break
            return c

        accesses = defaultdict(list)
        sympy_accesses = defaultdict(list)
        for var_name in self.kernel.variables:
            for r in self.kernel.sources.get(var_name, []):
                if r is None:
                    continue
                accesses[var_name].append(r)
                sympy_accesses[var_name].append(self.kernel.access_to_sympy(var_name, r))
            for w in self.kernel.destinations.get(var_name, []):
                if w is None:
                    continue
                accesses[var_name].append(w)
                sympy_accesses[var_name].append(self.kernel.access_to_sympy(var_name, w))
            # order accesses by increasing order
            accesses[var_name].sort(key=cmp_to_key(sympy_compare), reverse=True)

        results['accesses'] = accesses
        results['sympy_accesses'] = sympy_accesses

        # For each dimension (1D, 2D, 3D ... nD)
        for dimension in range(1, len(list(self.kernel.get_loop_stack()))+1):
            results['dimensions'][dimension] = {}

            slices = defaultdict(list)
            slices_accesses = defaultdict(list)
            for var_name in accesses:
                for a in accesses[var_name]:
                    # slices are identified by the tuple of indices of higher dimensions
                    slice_id = tuple([var_name, tuple(a[:-dimension])])
                    slices[slice_id].append(a)
                    slices_accesses[slice_id].append(self.kernel.access_to_sympy(var_name, a))
            results['dimensions'][dimension]['slices'] = slices
            results['dimensions'][dimension]['slices_accesses'] = slices_accesses

            slices_distances = defaultdict(list)
            for k, v in slices_accesses.items():
                for i in range(1, len(v)):
                    slices_distances[k].append((v[i] - v[i-1]).simplify())
            results['dimensions'][dimension]['slices_distances'] = slices_distances

            # Check that distances contain only free_symbols based on constants
            for dist in chain(*slices_distances.values()):
                if any([s not in self.kernel.constants.keys() for s in dist.free_symbols]):
                    raise ValueError("Some distances are not based on constants: "+str(dist))

            # Sum of lengths between relative distances
            slices_sum = sum([sum(dists) for dists in slices_distances.values()])
            results['dimensions'][dimension]['slices_sum'] = slices_sum

            # Max of lengths between relative distances
            # Work-around, the arguments with the most symbols get to stay
            # FIXME, may not be correct in all cases. e.g., N+M vs. N*M
            def FuckedUpMax(*args):
                if len(args) == 1:
                    return args[0]
                # expand all expressions:
                args = [a.expand() for a in args]
                # Filter expressions with less than the maximum number of symbols
                max_symbols = max([len(a.free_symbols) for a in args])
                args = list(filter(lambda a: len(a.free_symbols) == max_symbols, args))
                if max_symbols == 0:
                    return sympy.Max(*args)
                # Filter symbols with lower exponent
                max_coeffs = 0
                for a in args:
                    for s in a.free_symbols:
                        max_coeffs = max(max_coeffs, len(sympy.Poly(a, s).all_coeffs()))

                def coeff_filter(a):
                    return max(
                        0, 0,
                        *[len(sympy.Poly(a, s).all_coeffs()) for s in a.free_symbols]) == max_coeffs
                args = list(filter(coeff_filter, args))

                m = sympy.Max(*args)
                # if m.is_Function:
                #     raise ValueError("Could not resolve {} to maximum.".format(m))
                return m

            slices_max = FuckedUpMax(sympy.Integer(0),
                                     *[FuckedUpMax(*dists) for dists in slices_distances.values()])
            results['dimensions'][dimension]['slices_max'] = slices_max

            # Nmber of slices
            slices_count = len(slices_accesses)
            results['dimensions'][dimension]['slices_count'] = slices_count

            # Cache requirement expression
            cache_requirement_bytes = (slices_sum + slices_max*slices_count)*element_size
            results['dimensions'][dimension]['cache_requirement_bytes'] = cache_requirement_bytes
            # Apply to all cache sizes
            csim = self.machine.get_cachesim(self._args.cores)
            results['dimensions'][dimension]['caches'] = {}
            for cl in csim.levels(with_mem=False):
                cache_equation = sympy.Eq(cache_requirement_bytes, cl.size())
                if len(self.kernel.constants.keys()) <= 1:
                    inequality = sympy.solve(sympy.LessThan(cache_requirement_bytes, cl.size()),
                                             *self.kernel.constants.keys())
                else:
                    # Sympy does not solve for multiple constants
                    inequality = sympy.LessThan(cache_requirement_bytes, cl.size())
                try:
                    eq = sympy.solve(inequality, *self.kernel.constants.keys(), dict=True)
                except NotImplementedError:
                    eq = None
                results['dimensions'][dimension]['caches'][cl.name] = {
                    'cache_size': cl.size(),
                    'equation': cache_equation,
                    'lt': inequality,
                    'eq': eq
                }

        return results
def calculate_cache_access(self):
        """Apply layer condition model to calculate cache accesses."""
        # FIXME handle multiple datatypes
        element_size = self.kernel.datatypes_size[self.kernel.datatype]

        results = {'dimensions': {}}

        def sympy_compare(a, b):
            c = 0
            for i in range(min(len(a), len(b))):
                s = a[i] - b[i]
                if sympy.simplify(s > 0):
                    c = -1
                elif sympy.simplify(s == 0):
                    c = 0
                else:
                    c = 1
                if c != 0:
                    break
            return c

        accesses = defaultdict(list)
        sympy_accesses = defaultdict(list)
        for var_name in self.kernel.variables:
            for r in self.kernel.sources.get(var_name, []):
                if r is None:
                    continue
                accesses[var_name].append(r)
                sympy_accesses[var_name].append(self.kernel.access_to_sympy(var_name, r))
            for w in self.kernel.destinations.get(var_name, []):
                if w is None:
                    continue
                accesses[var_name].append(w)
                sympy_accesses[var_name].append(self.kernel.access_to_sympy(var_name, w))
            # order accesses by increasing order
            accesses[var_name].sort(key=cmp_to_key(sympy_compare), reverse=True)

        results['accesses'] = accesses
        results['sympy_accesses'] = sympy_accesses

        # For each dimension (1D, 2D, 3D ... nD)
        for dimension in range(1, len(list(self.kernel.get_loop_stack()))+1):
            results['dimensions'][dimension] = {}

            slices = defaultdict(list)
            slices_accesses = defaultdict(list)
            for var_name in accesses:
                for a in accesses[var_name]:
                    # slices are identified by the tuple of indices of higher dimensions
                    slice_id = tuple([var_name, tuple(a[:-dimension])])
                    slices[slice_id].append(a)
                    slices_accesses[slice_id].append(self.kernel.access_to_sympy(var_name, a))
            results['dimensions'][dimension]['slices'] = slices
            results['dimensions'][dimension]['slices_accesses'] = slices_accesses

            slices_distances = defaultdict(list)
            for k, v in slices_accesses.items():
                for i in range(1, len(v)):
                    slices_distances[k].append((v[i] - v[i-1]).simplify())
            results['dimensions'][dimension]['slices_distances'] = slices_distances

            # Check that distances contain only free_symbols based on constants
            for dist in chain(*slices_distances.values()):
                if any([s not in self.kernel.constants.keys() for s in dist.free_symbols]):
                    raise ValueError("Some distances are not based on constants: "+str(dist))

            # Sum of lengths between relative distances
            slices_sum = sum([sum(dists) for dists in slices_distances.values()])
            results['dimensions'][dimension]['slices_sum'] = slices_sum

            # Max of lengths between relative distances
            # Work-around, the arguments with the most symbols get to stay
            # FIXME, may not be correct in all cases. e.g., N+M vs. N*M
            def FuckedUpMax(*args):
                if len(args) == 1:
                    return args[0]
                # expand all expressions:
                args = [a.expand() for a in args]
                # Filter expressions with less than the maximum number of symbols
                max_symbols = max([len(a.free_symbols) for a in args])
                args = list(filter(lambda a: len(a.free_symbols) == max_symbols, args))
                if max_symbols == 0:
                    return sympy.Max(*args)
                # Filter symbols with lower exponent
                max_coeffs = 0
                for a in args:
                    for s in a.free_symbols:
                        max_coeffs = max(max_coeffs, len(sympy.Poly(a, s).all_coeffs()))

                def coeff_filter(a):
                    return max(
                        0, 0,
                        *[len(sympy.Poly(a, s).all_coeffs()) for s in a.free_symbols]) == max_coeffs
                args = list(filter(coeff_filter, args))

                m = sympy.Max(*args)
                # if m.is_Function:
                #     raise ValueError("Could not resolve {} to maximum.".format(m))
                return m

            slices_max = FuckedUpMax(sympy.Integer(0),
                                     *[FuckedUpMax(*dists) for dists in slices_distances.values()])
            results['dimensions'][dimension]['slices_max'] = slices_max

            # Nmber of slices
            slices_count = len(slices_accesses)
            results['dimensions'][dimension]['slices_count'] = slices_count

            # Cache requirement expression
            cache_requirement_bytes = (slices_sum + slices_max*slices_count)*element_size
            results['dimensions'][dimension]['cache_requirement_bytes'] = cache_requirement_bytes
            # Apply to all cache sizes
            csim = self.machine.get_cachesim(self._args.cores)
            results['dimensions'][dimension]['caches'] = {}
            for cl in csim.levels(with_mem=False):
                cache_equation = sympy.Eq(cache_requirement_bytes, cl.size())
                if len(self.kernel.constants.keys()) <= 1:
                    inequality = sympy.solve(sympy.LessThan(cache_requirement_bytes, cl.size()),
                                             *self.kernel.constants.keys())
                else:
                    # Sympy does not solve for multiple constants
                    inequality = sympy.LessThan(cache_requirement_bytes, cl.size())
                try:
                    eq = sympy.solve(inequality, *self.kernel.constants.keys(), dict=True)
                except NotImplementedError:
                    eq = None
                results['dimensions'][dimension]['caches'][cl.name] = {
                    'cache_size': cl.size(),
                    'equation': cache_equation,
                    'lt': inequality,
                    'eq': eq
                }

        return results
def calculate_cache_access ( self ) : # FIXME handle multiple datatypes element_size = self . kernel . datatypes_size [ self . kernel . datatype ] results = { 'dimensions' : { } } def sympy_compare ( a , b ) : c = 0 for i in range ( min ( len ( a ) , len ( b ) ) ) : s = a [ i ] - b [ i ] if sympy . simplify ( s > 0 ) : c = - 1 elif sympy . simplify ( s == 0 ) : c = 0 else : c = 1 if c != 0 : break return c accesses = defaultdict ( list ) sympy_accesses = defaultdict ( list ) for var_name in self . kernel . variables : for r in self . kernel . sources . get ( var_name , [ ] ) : if r is None : continue accesses [ var_name ] . append ( r ) sympy_accesses [ var_name ] . append ( self . kernel . access_to_sympy ( var_name , r ) ) for w in self . kernel . destinations . get ( var_name , [ ] ) : if w is None : continue accesses [ var_name ] . append ( w ) sympy_accesses [ var_name ] . append ( self . kernel . access_to_sympy ( var_name , w ) ) # order accesses by increasing order accesses [ var_name ] . sort ( key = cmp_to_key ( sympy_compare ) , reverse = True ) results [ 'accesses' ] = accesses results [ 'sympy_accesses' ] = sympy_accesses # For each dimension (1D, 2D, 3D ... nD) for dimension in range ( 1 , len ( list ( self . kernel . get_loop_stack ( ) ) ) + 1 ) : results [ 'dimensions' ] [ dimension ] = { } slices = defaultdict ( list ) slices_accesses = defaultdict ( list ) for var_name in accesses : for a in accesses [ var_name ] : # slices are identified by the tuple of indices of higher dimensions slice_id = tuple ( [ var_name , tuple ( a [ : - dimension ] ) ] ) slices [ slice_id ] . append ( a ) slices_accesses [ slice_id ] . append ( self . kernel . access_to_sympy ( var_name , a ) ) results [ 'dimensions' ] [ dimension ] [ 'slices' ] = slices results [ 'dimensions' ] [ dimension ] [ 'slices_accesses' ] = slices_accesses slices_distances = defaultdict ( list ) for k , v in slices_accesses . items ( ) : for i in range ( 1 , len ( v ) ) : slices_distances [ k ] . append ( ( v [ i ] - v [ i - 1 ] ) . simplify ( ) ) results [ 'dimensions' ] [ dimension ] [ 'slices_distances' ] = slices_distances # Check that distances contain only free_symbols based on constants for dist in chain ( * slices_distances . values ( ) ) : if any ( [ s not in self . kernel . constants . keys ( ) for s in dist . free_symbols ] ) : raise ValueError ( "Some distances are not based on constants: " + str ( dist ) ) # Sum of lengths between relative distances slices_sum = sum ( [ sum ( dists ) for dists in slices_distances . values ( ) ] ) results [ 'dimensions' ] [ dimension ] [ 'slices_sum' ] = slices_sum # Max of lengths between relative distances # Work-around, the arguments with the most symbols get to stay # FIXME, may not be correct in all cases. e.g., N+M vs. N*M def FuckedUpMax ( * args ) : if len ( args ) == 1 : return args [ 0 ] # expand all expressions: args = [ a . expand ( ) for a in args ] # Filter expressions with less than the maximum number of symbols max_symbols = max ( [ len ( a . free_symbols ) for a in args ] ) args = list ( filter ( lambda a : len ( a . free_symbols ) == max_symbols , args ) ) if max_symbols == 0 : return sympy . Max ( * args ) # Filter symbols with lower exponent max_coeffs = 0 for a in args : for s in a . free_symbols : max_coeffs = max ( max_coeffs , len ( sympy . Poly ( a , s ) . all_coeffs ( ) ) ) def coeff_filter ( a ) : return max ( 0 , 0 , * [ len ( sympy . Poly ( a , s ) . all_coeffs ( ) ) for s in a . free_symbols ] ) == max_coeffs args = list ( filter ( coeff_filter , args ) ) m = sympy . Max ( * args ) # if m.is_Function: #     raise ValueError("Could not resolve {} to maximum.".format(m)) return m slices_max = FuckedUpMax ( sympy . Integer ( 0 ) , * [ FuckedUpMax ( * dists ) for dists in slices_distances . values ( ) ] ) results [ 'dimensions' ] [ dimension ] [ 'slices_max' ] = slices_max # Nmber of slices slices_count = len ( slices_accesses ) results [ 'dimensions' ] [ dimension ] [ 'slices_count' ] = slices_count # Cache requirement expression cache_requirement_bytes = ( slices_sum + slices_max * slices_count ) * element_size results [ 'dimensions' ] [ dimension ] [ 'cache_requirement_bytes' ] = cache_requirement_bytes # Apply to all cache sizes csim = self . machine . get_cachesim ( self . _args . cores ) results [ 'dimensions' ] [ dimension ] [ 'caches' ] = { } for cl in csim . levels ( with_mem = False ) : cache_equation = sympy . Eq ( cache_requirement_bytes , cl . size ( ) ) if len ( self . kernel . constants . keys ( ) ) <= 1 : inequality = sympy . solve ( sympy . LessThan ( cache_requirement_bytes , cl . size ( ) ) , * self . kernel . constants . keys ( ) ) else : # Sympy does not solve for multiple constants inequality = sympy . LessThan ( cache_requirement_bytes , cl . size ( ) ) try : eq = sympy . solve ( inequality , * self . kernel . constants . keys ( ) , dict = True ) except NotImplementedError : eq = None results [ 'dimensions' ] [ dimension ] [ 'caches' ] [ cl . name ] = { 'cache_size' : cl . size ( ) , 'equation' : cache_equation , 'lt' : inequality , 'eq' : eq } return results
Apply layer condition model to calculate cache accesses.
Apply layer condition model to calculate cache accesses .