No valid solution found using the tutorial example

[ghostplant]

Source Code:

import tvm

def gemm(A, B):
    k = tvm.reduce_axis((0, B.shape[0]))
    return tvm.compute((A.shape[0], B.shape[1]), lambda i, j: tvm.sum(A[i, k] * B[k, j], axis=k))

def wrap_gemm(N, K, M):
    A = tvm.placeholder((N, K))
    B = tvm.placeholder((K, M))
    Output = gemm(A, B)
    return [Output.op], [A, B, Output]

from flextensor.task import register_task, Task
from flextensor.model import WalkerGroup
from flextensor.scheduler import schedule

if __name__ == '__main__':
  task = Task(
    "gemm",
    "gemm",
    wrap_gemm,
    (1024, 1024, 1024),
    "llvm",
    0)
  register_task(task)
  s, bufs, configs = schedule(
            task.key, # give the key of target task
            slevel=4,
            rlevel=3,
            op_trial=100,
            timeout=10,
            op_stop=30,
            method="searching",
            parallel=4,
            )

Output:

graph space size 1
op 0 space size: 43188288
[Warning] Directory lib is not empty, but reusing it
warm up [1584960963.652893] [ inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf ]
warm up [1584960977.754150] [ inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf ]
warm up [1584960991.611287] [ inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf ]
warm up [1584961005.486223] [ inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf ]
warm up [1584961019.563355] [ inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf ]
warm up [1584961033.576784] [ inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf ]
warm up [1584961047.659202] [ inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf ]
warm up [1584961061.669718] [ inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf ]
warm up [1584961075.572861] [ inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf ]
warm up [1584961089.390276] [ inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf ]
warm up [1584961103.236112] [ inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf ]
warm up [1584961117.260888] [ inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf ]
warm up [1584961131.503041] [ inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf ]
warm up [1584961145.477987] [ inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf ]
warm up [1584961159.549252] [ inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf ]
warm up [1584961173.469501] [ inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf ]
warm up [1584961187.413991] [ inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf ]
warm up [1584961201.389768] [ inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf ]
warm up [1584961215.701637] [ inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf ]
warm up [1584961230.179169] [ inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf ]
Warning: No valid schedule found in warm up process, please use more trials
Now automatically use more trials, increase 20
warm up [1584961244.064868] [ inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf ]
Warning: No valid schedule found in warm up process, please use more trials
Now automatically use more trials, increase 20
warm up [1584961257.944109] [ inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf ]
Warning: No valid schedule found in warm up process, please use more trials
Now automatically use more trials, increase 20
warm up [1584961271.798598] [ inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf ]
Warning: No valid schedule found in warm up process, please use more trials
Now automatically use more trials, increase 20
warm up [1584961285.662753] [ inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf ]
Warning: No valid schedule found in warm up process, please use more trials
...
...

[wyc-ruiker]

I have the same problem. @KnowingNothing Could you help us?

[KnowingNothing]

This is a small bug and I have checked in a fix for this. BTW, if you want to try some advanced searching, please take a look at flextensor/optimize directory. For example, you can try optimize_conv2d.py with the following command:

python optimize_conv2d.py --shapes yolo --target cuda --trials 1000 --timeout 10 --parallel 8 --log tmp_log.txt

The meanings of different options are:

--shapes: input shapes for conv2d, pre-defined in `configs/conv2d_config.py`
--target: run on which hardware
--trials: number of trials in searching, recommend >= 1000
--timeout: timeout threshold for single point (in seconds)
--parallel: number of parallel runners
--log: dump final schedule config to file

[jinluyang]

I found it has maybe the same bug of "No valid schedule found"for the optimize_conv2d example. BTW, tvm has modified its namespace in Febrary, which makes Flextensor unavailable for the newest tvm. Perhaps we should limit the tvm version in README.md

[KnowingNothing]

I have added the constraint for TVM (<=v0.6).
I can run optimize_conv2d.py without problems, could you provide more information about your system settings and error message?

[Maximilianxu]

@KnowingNothing Same issue here.
Just a simple conv2d test.

import tvm
from tvm import te
import numpy as np
from flextensor.task import register_task, Task

if __name__ == '__main__':
  N = 1
  I, O, H, W = 16, 32, 128, 128
  KH, KW = 3, 3
  STRIDE = 1

  def conv2d(inpf, kernel):
    rh, rw, ri = te.reduce_axis((0, KH)), te.reduce_axis((0, KW)), te.reduce_axis((0, I))
    outf = te.compute((N, O, H, W), 
      lambda n, o, h, w: te.sum(inpf[n][STRIDE * h + rh][STRIDE * w + rw][ri] * kernel[o][ri][rh][rw],
      [ri, rh, rw]))
    return outf

  def wrap_conv2d():
    inpf = te.placeholder((N, (H - 1) * STRIDE + KH, (W - 1) * STRIDE + KW, I))
    kernel = te.placeholder((O, I, KH, KW))
    outf = conv2d(inpf, kernel)
    return [outf.op], [inpf, kernel, outf]

  task = Task(
      "flex_conv2d", 
      "flex_conv2d", 
      wrap_conv2d, 
      (), 
      "llvm", 
      0)
  # register the task
  register_task(task)

  from flextensor.scheduler import schedule

  s, bufs, configs = schedule(
              task.key, # give the key of target task
              slevel=4,
              rlevel=3,
              op_trial=200, 
              timeout=4, 
              op_stop=30, 
              method="q", 
              parallel=6,
              )

  #directly use the results
  func = tvm.build(s, bufs, task.target)

  import json
  with open('configs.data', 'w') as conf_file:
    conf_file.write(json.dumps(configs._asdict()))
  from flextensor.utils import Config
  # use the configs
  from flextensor.scheduler import schedule_with_config
  with open('configs.data') as file:
    configs = Config(**json.load(file))
  s, bufs = schedule_with_config(task.key, configs)
  func = tvm.build(s, bufs, task.target)

  np_inpf = np.random.uniform(size=(N, (H - 1) * STRIDE + KH, (W - 1) * STRIDE + KW, I))
  np_knl = np.random.uniform(size=(O, I, KH, KW))

  tvm_inpf = tvm.nd.array(np_inpf.astype(np.float32))
  tvm_knl = tvm.nd.array(np_knl.astype(np.float32))
  tvm_outf = tvm.nd.array(np.zeros((N, O, H, W), dtype=np.float32))
  ctx = tvm.cpu()
  evaluator = func.time_evaluator(func.entry_name, ctx, number=10)
  print('FlexTensor performance conv2d: %f ms' % (evaluator(tvm_inpf, tvm_knl, tvm_outf).mean * 1e3))

Error log:

graph space size 1
op 0 space size: 3612672000
[Warning] Directory lib is not empty, but reusing it
warm up [1595492612.970399] [ inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf ]
warm up [1595492621.818268] [ inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf ]
warm up [1595492630.110075] [ inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf ]
warm up [1595492638.380301] [ inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf ]
warm up [1595492647.012408] [ inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf ]
warm up [1595492655.634856] [ inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf ]
warm up [1595492664.408054] [ inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf ]
warm up [1595492673.263167] [ inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf ]
warm up [1595492682.083639] [ inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf ]
warm up [1595492690.733876] [ inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf ]
Warning: No valid schedule found in warm up process, please use more trials
Now automatically use more trials, increase 20
warm up [1595492699.353486] [ inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf ]
Warning: No valid schedule found in warm up process, please use more trials
Now automatically use more trials, increase 20
warm up [1595492708.211909] [ inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf ]
Warning: No valid schedule found in warm up process, please use more trials
Now automatically use more trials, increase 20
warm up [1595492717.213636] [ inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf ]
Warning: No valid schedule found in warm up process, please use more trials
Now automatically use more trials, increase 20
warm up [1595492727.293403] [ inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf ]
Warning: No valid schedule found in warm up process, please use more trials
Now automatically use more trials, increase 20
warm up [1595492736.475262] [ inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf ]
Warning: No valid schedule found in warm up process, please use more trials
Now automatically use more trials, increase 20
warm up [1595492745.092825] [ inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf ]
Warning: No valid schedule found in warm up process, please use more trials
Now automatically use more trials, increase 20
warm up [1595492753.771646] [ inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf ]
Warning: No valid schedule found in warm up process, please use more trials
Now automatically use more trials, increase 20
warm up [1595492762.784351] [ inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf ]
Warning: No valid schedule found in warm up process, please use more trials
Now automatically use more trials, increase 20
warm up [1595492772.444309] [ inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf ]
Warning: No valid schedule found in warm up process, please use more trials
Now automatically use more trials, increase 20
warm up [1595492781.729871] [ inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf ]
Warning: No valid schedule found in warm up process, please use more trials
Now automatically use more trials, increase 20
warm up [1595492790.622237] [ inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf ]
Warning: No valid schedule found in warm up process, please use more trials
Now automatically use more trials, increase 20
warm up [1595492799.540891] [ inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf ]
Warning: No valid schedule found in warm up process, please use more trials
Now automatically use more trials, increase 20
warm up [1595492808.155284] [ inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf ]
Warning: No valid schedule found in warm up process, please use more trials
Now automatically use more trials, increase 20
warm up [1595492817.201742] [ inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf ]
Warning: No valid schedule found in warm up process, please use more trials
Now automatically use more trials, increase 20
warm up [1595492826.537709] [ inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf ]
Warning: No valid schedule found in warm up process, please use more trials
Now automatically use more trials, increase 20
warm up [1595492835.257115] [ inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf ]
Warning: No valid schedule found in warm up process, please use more trials
Now automatically use more trials, increase 20
warm up [1595492844.165177] [ inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf ]
Warning: No valid schedule found in warm up process, please use more trials
Now automatically use more trials, increase 20
warm up [1595492852.796793] [ inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf ]
Warning: No valid schedule found in warm up process, please use more trials
Now automatically use more trials, increase 20
warm up [1595492861.677269] [ inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf ]
Warning: No valid schedule found in warm up process, please use more trials
Now automatically use more trials, increase 20
Fail to find valid schedule, too many errors
Traceback (most recent call last):

  File "flex_conv2d.py", line 51, in <module>
    parallel=6,

  File "/home/zyx/workspaces/python/FlexTensor/flextensor/scheduler.py", line 2100, in schedule
    perf_path=perf_path,

  File "/home/zyx/workspaces/python/FlexTensor/flextensor/scheduler.py", line 670, in schedule
    return self._q_schedule(configs, wanted_types, use_model=use_model)

  File "/home/zyx/workspaces/python/FlexTensor/flextensor/scheduler.py", line 443, in _q_schedule
    from_lst, next_points, action_lst = self.walker_group.walk(cur_lst, trial)

  File "/home/zyx/workspaces/python/FlexTensor/flextensor/model.py", line 359, in walk
    next_index_lst, direction_lst = self.walkers[name].walk(flattened_lst, index_lst, trial, epsilon, gamma)

  File "/home/zyx/workspaces/python/FlexTensor/flextensor/model.py", line 72, in walk
    q_values_lst = self.pre_judger(torch.FloatTensor(inputs)).detach()

  File "/home/zyx/.local/lib/python3.6/site-packages/torch/nn/modules/module.py", line 550, in __call__
    result = self.forward(*input, **kwargs)

  File "/home/zyx/workspaces/python/FlexTensor/flextensor/model.py", line 34, in forward
    out = self.net(inputs)

  File "/home/zyx/.local/lib/python3.6/site-packages/torch/nn/modules/module.py", line 550, in __call__
    result = self.forward(*input, **kwargs)

  File "/home/zyx/.local/lib/python3.6/site-packages/torch/nn/modules/container.py", line 100, in forward
    input = module(input)

  File "/home/zyx/.local/lib/python3.6/site-packages/torch/nn/modules/module.py", line 550, in __call__
    result = self.forward(*input, **kwargs)

  File "/home/zyx/.local/lib/python3.6/site-packages/torch/nn/modules/linear.py", line 87, in forward
    return F.linear(input, self.weight, self.bias)

  File "/home/zyx/.local/lib/python3.6/site-packages/torch/nn/functional.py", line 1612, in linear
    output = input.matmul(weight.t())

RuntimeError: size mismatch, m1: [1 x 0], m2: [30 x 64] at /pytorch/aten/src/TH/generic/THTensorMath.cpp:41

I also tried to add this shape config to yolo_shapes in conv_config.py and run python3 optimize_conv2d.py in your "optimize/" directory, same issue encountered.

My TVM version is 0.7dev1, but I don't think this problem is due to the TVM version. It seems that there are some bugs in your scheduling template (the cpu_schedule_simple func) and many invalid configs are actually valid configs.

May you have any ideas? Thanks in advance.

[KnowingNothing]

I can reproduce your issue and I have pushed a fix for it. There are 3 template generators for CPU in FlexTensor, and the current new one is not well tested (with index out of range). My new fix should address the 'index out of range' problems, and it works on my local machine when running optimize_conv2d.py.
If you want to run an example just like that in README, please refer to this issue.
Another advice is to use a large timeout for CPU backend (e.g. --timeout 20)

[Maximilianxu]

@KnowingNothing I think there are still some bugs in the newest template cpu_schedule_simple. Seems due to "compute_at" for "write_cache".
Error log:

==>DEBUG: invalid config: [{'fuse': [], 'spatial': [[1, 1, 1, 1], [1, 1, 1, 32], [1, 1, 1, 128], [1, 1, 1, 128]], 'reduce': [[1, 1, 1, 16], [1, 1, 1, 3], [1, 1, 1, 3]], 'reorder': [], 'inline': [], 'unroll': [[0, 0]], 'merge': [], 'special': []}] Traceback (most recent call last):
  [bt] (3) /home/zyx/workspaces/python/tvm/build/libtvm.so(TVMFuncCall+0x65) [0x7f856ee9ee55]
  [bt] (2) /home/zyx/workspaces/python/tvm/build/libtvm.so(tvm::runtime::TypedPackedFunc<tvm::te::Stage& (tvm::te::Stage, tvm::te::Stage, tvm::tir::IterVar)>::AssignTypedLambda<tvm::runtime::Registry::set_body_method<tvm::te::Stage, tvm::te::Stage&, tvm::te::Stage, tvm::tir::IterVar>(tvm::te::Stage& (tvm::te::Stage::*)(tvm::te::Stage, tvm::tir::IterVar))::{lambda(tvm::te::Stage, tvm::te::Stage, tvm::tir::IterVar)#1}>(tvm::runtime::Registry::set_body_method<tvm::te::Stage, tvm::te::Stage&, tvm::te::Stage, tvm::tir::IterVar>(tvm::te::Stage& (tvm::te::Stage::*)(tvm::te::Stage, tvm::tir::IterVar))::{lambda(tvm::te::Stage, tvm::te::Stage, tvm::tir::IterVar)#1})::{lambda(tvm::runtime::TVMArgs const&, tvm::runtime::TVMRetValue*)#1}::operator()(tvm::runtime::TVMArgs const, tvm::runtime::TVMRetValue) const+0x1c0) [0x7f856e71d490]
  [bt] (1) /home/zyx/workspaces/python/tvm/build/libtvm.so(tvm::te::Stage::compute_at(tvm::te::Stage, tvm::tir::IterVar)+0x2d1) [0x7f856e7086a1]
  [bt] (0) /home/zyx/workspaces/python/tvm/build/libtvm.so(dmlc::LogMessageFatal::~LogMessageFatal()+0x7c) [0x7f856e4dfaac]
  File "/home/zyx/workspaces/python/tvm/src/te/schedule/schedule_lang.cc", line 143
TVMError: Check failed: found: Cannot find the axis (nullptr) in parent's leaf_iter_vars parent=stage(output, 0x404fa10)

The operator is the same as the above conv2d test.

BTW, do you have any ideas why some configs building are so slow?

Here are some slow configs for the cpu_schedule_simple template. It stucks at tvm.build function.

 1. [{'fuse': [], 
 'spatial': [[1, 1, 1, 1], [4, 1, 4, 2], [4, 1, 4, 8], [32, 2, 1, 2]], 
 'reduce': [[1, 1, 8, 2], [1, 1, 1, 3], [1, 3, 1, 1]], 
 'reorder': [], 
 'inline': [], 
 'unroll': [[1, 0]], 
 'merge': [], 
 'special': []}]
 2. [{'fuse': [], 
 'spatial': [[1, 1, 1, 1], [1, 1, 16, 2], [8, 4, 4, 1], [2, 2, 2, 16]], 
 'reduce': [[4, 1, 1, 4], [1, 3, 1, 1], [1, 1, 1, 3]], 
 'reorder': [], 
 'inline': [], 
 'unroll': [[1500, 0]], 
 'merge': [], 
 'special': []}]
 3. [{'fuse': [], 
 'spatial': [[1, 1, 1, 1], [1, 2, 4, 4], [1, 4, 32, 1], [1, 32, 4, 1]], 
 'reduce': [[1, 4, 2, 2], [1, 1, 1, 3], [1, 3, 1, 1]], 
 'reorder': [], 
 'inline': [], 
 'unroll': [[1, 1]], 
 'merge': [], 
 'special': []}]
 4. [{'fuse': [], 
 'spatial': [[1, 1, 1, 1], [1, 16, 2, 1], [4, 2, 2, 8], [16, 1, 8, 1]], 
 'reduce': [[1, 2, 8, 1], [1, 1, 1, 3], [1, 1, 1, 3]], 
 'reorder': [], 
 'inline': [], 
 'unroll': [[512, 0]], 
 'merge': [], 
 'special': []}]
 5. [{'fuse': [], 
 'spatial': [[1, 1, 1, 1], [1, 2, 8, 2], [2, 8, 2, 4], [1, 2, 16, 4]], 
 'reduce': [[1, 2, 1, 8], [1, 3, 1, 1], [1, 3, 1, 1]], 
 'reorder': [], 
 'inline': [], 
 'unroll': [[1500, 0]], 
 'merge': [], 
 'special': []}]
 6. [{'fuse': [], 
 'spatial': [[1, 1, 1, 1], [4, 1, 4, 2], [2, 16, 2, 2], [1, 1, 2, 64]], 
 'reduce': [[2, 8, 1, 1], [3, 1, 1, 1], [3, 1, 1, 1]], 
 'reorder': [], 
 'inline': [], 
 'unroll': [[512, 1]], 
 'merge': [], 
 'special': []}]

[KnowingNothing]

I'll look into this error. Before that, I recommend you to use the old template generators for CPU backends.
It's true that TVM's build is slow, usually requires hundreds of milliseconds. Sometimes it stucks due to the problem of multiprocessing. The building and executing workflow in FlexTensor can be greatly optimized. The multiprocessing context is 'spawn', if you use 'fork', the overhead of multiprocessing will become smaller, but the cost is that you can't do more than one schedule task at a time (which is supported using 'spawn').

[Maximilianxu]

@KnowingNothing Thanks. I see, but the above slow configs are built sequencetially (I didn't use your multiprocessing context), and each of them is very slow. As for setting timeout for subprocesses, you can try pebble, this package is very nice.

[KnowingNothing]

Great. Thanks for your suggestion.