AutoTVM how is the search space being generated

AkhilJ99 · September 24, 2020, 7:15am

After looking at the tutorial for auto tuning in auto tvm, there seems to two methods to create a search space, one where the user gives an array if possible values to search and the other where tvm generates this space. In the latter case how does tvm model the search space equation, or is just a brute force listing of all possible values ?. Also whats is the difference between auto scheduling and auto tvm, arent both trying to search for the best parameters in the search space ?.

Now after the search space is defined what parameters are used to decide which config is the best, is it just execution time ?.

comaniac · September 24, 2020, 5:51pm

The search space is defined in the schedule template, such as:

github.com

apache/incubator-tvm/blob/master/python/tvm/topi/cuda/conv2d_direct.py#L31


from tvm import autotvm
from ..util import get_const_tuple


def schedule_direct_cuda(cfg, s, conv):
    """schedule optimized for batch size = 1"""

    ##### space definition begin #####
    n, f, y, x = s[conv].op.axis
    rc, ry, rx = s[conv].op.reduce_axis
    cfg.define_split("tile_f", f, num_outputs=4)
    cfg.define_split("tile_y", y, num_outputs=4)
    cfg.define_split("tile_x", x, num_outputs=4)
    cfg.define_split("tile_rc", rc, num_outputs=2)
    cfg.define_split("tile_ry", ry, num_outputs=2)
    cfg.define_split("tile_rx", rx, num_outputs=2)
    cfg.define_knob("auto_unroll_max_step", [0, 512, 1500])

    target = tvm.target.Target.current()
    if target.kind.name in ["nvptx", "rocm"]:
        cfg.define_knob("unroll_explicit", [1])

This line defines a search parameter, and the candidates are the factors of the length of f.

While AutoTVM needs schedule templates defined in TOPI, auto-scheduler generates schedules from scratch. As a result, the auto-scheduler generated schedules are more flexible and expected to achieve even better performance.
The execution time is the main metric to judge the schedule quality.

AkhilJ99 · September 25, 2020, 4:50am

Hey @comaniac Thanks. Are the hardware parameters like (num of threads, cache size) taken into consideration when auto scheduling is used. Also how does auto scheduling generate schedules from scratch (ie while executing the matrix multiplication example it prints a bunch of programs that it has generated as candidates how is this done). Does it look at every loop and try to figure out the best transformation based on execution time / GFLOPS ?.

Also the docs mentioned that XG boost model is used to to pick the next config from the config space (while tuning), Does this model only take the config space as an input and its loss based on execution time ?

comaniac · September 25, 2020, 6:26pm

For auto-schedule details, you can refer to the paper: https://arxiv.org/abs/2006.06762
XGBoost model also takes some features extracted from the TIR.

AkhilJ99 · September 27, 2020, 6:08am

Hey @comaniac thanks for the reference it as very helpful in understanding what the auto scheduler does. I had a few doubts

Is this auto scheduler already implemented in TVM or is it ongoing, as we were going through some of the files in the auto scheduler folder (https://github.com/apache/incubator-tvm/blob/master/python/tvm/auto_scheduler/measure.py) Many of the funtions are not implemented.
The hardwareparams class implemented in python/tvm/auto_scheduler/auto_schedule.py, are these parameters used while generating the schedule space (by introducing some sort of constrain on the space) or in the cost model

comaniac · September 27, 2020, 6:41am

All functions are implemented already. Many of them are implemented in C++. Is this what you’re looking for?

github.com

apache/incubator-tvm/blob/master/src/auto_scheduler/measure.cc

/*
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License.  You may obtain a copy of the License at
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing,
 * software distributed under the License is distributed on an
 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 * KIND, either express or implied.  See the License for the
 * specific language governing permissions and limitations
 * under the License.
 */

/*!

This file has been truncated. show original

Most of them used in the cost model at this moment.

AkhilJ99 · September 27, 2020, 6:57am

Thanks a lot @comaniac . Where could one get started when trying to add their own rules to generate sketches for new hardware ?.

as mentioned in the paper (section 4.1)

On the other hand, the derivation-based sketch generation in Ansor is flexible enough to generate the required structures for emerging algorithms and hardware, as we allow users to register new derivation rules and integrate them seamlessly with existing rules.

comaniac · September 27, 2020, 7:03am

Since the upstream of auto-scheduler is still in progress (~90%), we do not have a clean interface for users to add new sketch generation rules yet. The easiest way for now is referring or modifying an existing rule, such as:

https://github.com/apache/incubator-tvm/search?q=RuleAlwaysInline

jcf94 · September 28, 2020, 1:59am

The custom sketch rule support is ready in our develop branch, while the final user interface for it has not been decided yet.

If this is important for you, we can consider to upstream a experimental version of custom sketch.

cc @comaniac @merrymercy

AkhilJ99 · September 29, 2020, 7:48am

Hey @jcf94 and @comaniac thanks for the response , I was just trying to learn the compiler flow of tvm and how if needed new rules could be added which are hardware specific, As of now there is no immediate need, but thanks nevertheless.