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
Apply layer condition model to calculate cache accesses.