(self, optree)
return stacks
Split an optree to stacks.
Split an optree to stacks.
Split an optree to stacks .
def _split_to_stacks(self, optree):
        """
        Split an optree to stacks.
        """
        # post-order traversal
        whole_stack = optree.traverse(list())

        # build stages, each stage contains a sub optree
        stages = []
        main_stage = []
        main_stage_axis = []

        # get minority axis for binary operation default, suports axis 0 and 1
        axis_count = [0, 0]
        for s in whole_stack:
            if isinstance(s, dict) and s['op'] in OpCollection.reduction_ops:
                assert s['axis'] == 0 or s['axis'] == 1
                axis_count[s['axis']] += 1
        minority_axis = 0 if axis_count[0] <= axis_count[1] else 1

        # traverse stack and split stages
        for s in whole_stack:
            if isinstance(s, dict):
                if s['op'] == 'dot':
                    # convert left and right child to tensor when it was not
                    right = main_stage.pop()
                    main_stage_axis.pop()  # don't care the value
                    left = main_stage.pop()
                    main_stage_axis.pop()  # don't care the value
                    if isinstance(left, OpTreeNode):
                        left_buf = self._buf_malloc(left.shape)
                        stages.append(OpTreeNode({"op": "assign"}, left_buf,
                                                 left))
                        left = left_buf
                    if isinstance(right, OpTreeNode):
                        right_buf = self._buf_malloc(right.shape)
                        stages.append(OpTreeNode({"op": "assign"}, right_buf,
                                                 right))
                        right = right_buf
                    # buffer to store the result of dot
                    buf = self._buf_malloc((left.shape[0], right.shape[1]))
                    # save to stages
                    stages.append(OpTreeNode({"op": "assign"}, buf,
                                             OpTreeNode(s, left, right)))
                    # push buf to main_stage
                    main_stage.append(buf)
                    main_stage_axis.append(None)
                elif s['op'] == 'transpose':
                    # the object being transposed must be optree here
                    operand = main_stage.pop()
                    main_stage_axis.pop()  # don't care the value
                    # allocate buf for the operand shape
                    buf = self._buf_malloc(operand.shape)
                    # evaluate to buf
                    stages.append(OpTreeNode({"op": "assign"}, buf, operand))
                    # put the buf back to main_stage
                    main_stage.append(buf.T)
                    main_stage_axis.append(None)
                elif s['op'] in OpCollection.reduction_ops:
                    # since 2d reduction is converted
                    assert s['axis'] is not None
                    operand = main_stage.pop()
                    prev_axis = main_stage_axis.pop()
                    if prev_axis is not None and prev_axis != s['axis']:
                        # put everything under previous reduction to buf
                        buf = self._buf_malloc(operand.shape)
                        stages.append(
                            OpTreeNode({"op": "assign"}, buf, operand))
                        # put the buf with current reduction to main stage
                        main_stage.append(OpTreeNode(s, buf, None))
                        main_stage_axis.append(s['axis'])
                    else:
                        # do standary OpCollection.unary_ops
                        main_stage.append(OpTreeNode(s, operand, None))
                        main_stage_axis.append(s['axis'])
                elif s['op'] in OpCollection.unary_ops:
                    # will not run into multiple-axis reduction problem
                    # just pop, build optree and put back
                    operand = main_stage.pop()
                    axis = main_stage_axis.pop()
                    main_stage.append(OpTreeNode(s, operand, None))
                    main_stage_axis.append(axis)  # cancelled out
                elif s['op'] in OpCollection.binary_ops:  # not dot
                    # binary ops might run into multiple-axis reduction
                    right = main_stage.pop()
                    prev_axis_right = main_stage_axis.pop()
                    left = main_stage.pop()
                    prev_axis_left = main_stage_axis.pop()
                    if (prev_axis_right is not None and
                            prev_axis_left is not None and
                            prev_axis_left != prev_axis_right):
                        # do reduction on minority axis
                        if prev_axis_left == minority_axis:
                            buf = self._buf_malloc(left.shape)
                            stages.append(
                                OpTreeNode({"op": "assign"}, buf, left))
                            left = buf
                            axis = prev_axis_right
                        else:
                            buf = self._buf_malloc(right.shape)
                            stages.append(
                                OpTreeNode({"op": "assign"}, buf, right))
                            right = buf
                            axis = prev_axis_left
                        # append to main stage
                        main_stage.append(OpTreeNode(s, left, right))
                        main_stage_axis.append(axis)
                    else:
                        # no multiple-axis reduction, perform standard process
                        main_stage.append(OpTreeNode(s, left, right))
                        axis = None
                        if prev_axis_left is not None:
                            axis = prev_axis_left
                        else:
                            axis = prev_axis_right
                        main_stage_axis.append(axis)
                else:
                    return NotImplemented
            else:
                # tensor or scalars, just push to main_stage
                main_stage.append(s)
                main_stage_axis.append(None)

        # append the the laste stage
        stages.append(main_stage[0])

        # build stacks for call_compound_kernel
        stacks = []
        for stage in stages:
            # now all stages is exact one simple optree
            assert(isinstance(stage, OpTreeNode))
            # create stack
            stacks.append(stage.traverse(list()))

        # free buffer from buf_active to buf, without loosing the reference
        self._buf_free()

        return stacks
def _split_to_stacks ( self , optree ) : # post-order traversal whole_stack = optree . traverse ( list ( ) ) # build stages, each stage contains a sub optree stages = [ ] main_stage = [ ] main_stage_axis = [ ] # get minority axis for binary operation default, suports axis 0 and 1 axis_count = [ 0 , 0 ] for s in whole_stack : if isinstance ( s , dict ) and s [ 'op' ] in OpCollection . reduction_ops : assert s [ 'axis' ] == 0 or s [ 'axis' ] == 1 axis_count [ s [ 'axis' ] ] += 1 minority_axis = 0 if axis_count [ 0 ] <= axis_count [ 1 ] else 1 # traverse stack and split stages for s in whole_stack : if isinstance ( s , dict ) : if s [ 'op' ] == 'dot' : # convert left and right child to tensor when it was not right = main_stage . pop ( ) main_stage_axis . pop ( ) # don't care the value left = main_stage . pop ( ) main_stage_axis . pop ( ) # don't care the value if isinstance ( left , OpTreeNode ) : left_buf = self . _buf_malloc ( left . shape ) stages . append ( OpTreeNode ( { "op" : "assign" } , left_buf , left ) ) left = left_buf if isinstance ( right , OpTreeNode ) : right_buf = self . _buf_malloc ( right . shape ) stages . append ( OpTreeNode ( { "op" : "assign" } , right_buf , right ) ) right = right_buf # buffer to store the result of dot buf = self . _buf_malloc ( ( left . shape [ 0 ] , right . shape [ 1 ] ) ) # save to stages stages . append ( OpTreeNode ( { "op" : "assign" } , buf , OpTreeNode ( s , left , right ) ) ) # push buf to main_stage main_stage . append ( buf ) main_stage_axis . append ( None ) elif s [ 'op' ] == 'transpose' : # the object being transposed must be optree here operand = main_stage . pop ( ) main_stage_axis . pop ( ) # don't care the value # allocate buf for the operand shape buf = self . _buf_malloc ( operand . shape ) # evaluate to buf stages . append ( OpTreeNode ( { "op" : "assign" } , buf , operand ) ) # put the buf back to main_stage main_stage . append ( buf . T ) main_stage_axis . append ( None ) elif s [ 'op' ] in OpCollection . reduction_ops : # since 2d reduction is converted assert s [ 'axis' ] is not None operand = main_stage . pop ( ) prev_axis = main_stage_axis . pop ( ) if prev_axis is not None and prev_axis != s [ 'axis' ] : # put everything under previous reduction to buf buf = self . _buf_malloc ( operand . shape ) stages . append ( OpTreeNode ( { "op" : "assign" } , buf , operand ) ) # put the buf with current reduction to main stage main_stage . append ( OpTreeNode ( s , buf , None ) ) main_stage_axis . append ( s [ 'axis' ] ) else : # do standary OpCollection.unary_ops main_stage . append ( OpTreeNode ( s , operand , None ) ) main_stage_axis . append ( s [ 'axis' ] ) elif s [ 'op' ] in OpCollection . unary_ops : # will not run into multiple-axis reduction problem # just pop, build optree and put back operand = main_stage . pop ( ) axis = main_stage_axis . pop ( ) main_stage . append ( OpTreeNode ( s , operand , None ) ) main_stage_axis . append ( axis ) # cancelled out elif s [ 'op' ] in OpCollection . binary_ops : # not dot # binary ops might run into multiple-axis reduction right = main_stage . pop ( ) prev_axis_right = main_stage_axis . pop ( ) left = main_stage . pop ( ) prev_axis_left = main_stage_axis . pop ( ) if ( prev_axis_right is not None and prev_axis_left is not None and prev_axis_left != prev_axis_right ) : # do reduction on minority axis if prev_axis_left == minority_axis : buf = self . _buf_malloc ( left . shape ) stages . append ( OpTreeNode ( { "op" : "assign" } , buf , left ) ) left = buf axis = prev_axis_right else : buf = self . _buf_malloc ( right . shape ) stages . append ( OpTreeNode ( { "op" : "assign" } , buf , right ) ) right = buf axis = prev_axis_left # append to main stage main_stage . append ( OpTreeNode ( s , left , right ) ) main_stage_axis . append ( axis ) else : # no multiple-axis reduction, perform standard process main_stage . append ( OpTreeNode ( s , left , right ) ) axis = None if prev_axis_left is not None : axis = prev_axis_left else : axis = prev_axis_right main_stage_axis . append ( axis ) else : return NotImplemented else : # tensor or scalars, just push to main_stage main_stage . append ( s ) main_stage_axis . append ( None ) # append the the laste stage stages . append ( main_stage [ 0 ] ) # build stacks for call_compound_kernel stacks = [ ] for stage in stages : # now all stages is exact one simple optree assert ( isinstance ( stage , OpTreeNode ) ) # create stack stacks . append ( stage . traverse ( list ( ) ) ) # free buffer from buf_active to buf, without loosing the reference self . _buf_free ( ) return stacks