Nano Hash - криптовалюты, майнинг, программирование

Почему эта программа проверки двоичного дерева Risc-V не работает?

Я пытаюсь написать средство проверки дерева Risc-V: каждый узел дерева состоит из трех слов:

1) Либо 0, либо 1

2) Адрес левого узла

3) Адрес правого узла

Моя программа должна исследовать дерево и возвращать, насколько глубоко в дереве находится первый узел с 1 в качестве первого слова, вот код:

.data
tree:   .word n01
n01:    .word 0, n02, n03
n02:    .word 0, n04, n05
n03:    .word 0, n06, n07
n04:    .word 0, 0, 0
n05:    .word 0, 0, 0
n06:    .word 1, 0, 0
n07:    .word 0, 0, 0
.text
    lw a0, tree
    jal altezza
    addi a0, a0, -1
    li a7, 1
    ecall
    li a7, 10
    ecall

altezza:
    bne a0, zero, altezza_ric  
    jalr zero, ra, 0    

altezza_ric:
    addi sp, sp, -12  
    lw t1, 0(a0)
    sw ra, 0(sp)    
    bne t1, zero, skip_numb

    sw a0, 4(sp)    
    lw a0, 4(a0)    
    jal altezza
    sw a0, 8(sp)    
    lw a0, 4(sp)    
    lw a0, 8(a0)    
    jal altezza

    lw t0, 8(sp)    
    bne a0, zero, scelta
    mv a0, t0
    bne a0, zero, scelta
    jal skip
scelta:
    ble a0,t0,skip_add
    mv a0, t0


skip_add:  
    addi a0, a0, 1  #ad a0 inremento 1
skip:   lw ra, 0(sp)
    addi sp, sp, 12 
    jalr zero, ra, 0    

skip_numb:
    add a0, zero, zero
    jal skip_add
assembly riscv binary-tree
20.05.2020

Ответы:


1

Попробуйте выполнить пошаговое выполнение в отладчике, чтобы увидеть, дает ли каждая инструкция желаемый эффект.

Сделайте ваши начальные тестовые примеры как можно меньше, потому что отладка рекурсивных функций может быть очень запутанной. Так что попробуйте, например, только с одним узлом; затем только два узла (например, корневой узел с левым; корневой узел с правым).

В конце концов вы увидите это:

lw a0, 4(sp)    <------- the result of this load is discarded
lw a0, 8(a0)

Здесь первая загрузка не имеет смысла, потому что полученное ею значение a0 (немедленно) перезаписывается второй загрузкой.

    bne a0, zero, scelta
    jal skip
scelta:
    ble a0,t0,skip_add
    mv a0, t0
skip_add:

Не используйте jal для простого ветвления, вместо этого используйте j. Хотя здесь это не повредит, он обновляет ra, что вам не нужно в контексте простого if-then-else. Если бы у вас была конечная функция, которая не сохраняет ra в стеке, это было бы плохо.

Поскольку в этой последовательности есть условная ветвь, которая перескакивает через безусловную ветвь, ее можно упростить, исключив безусловную ветвь и метку (scelta:) следующим образом:

    beq a0, zero, skip  <--- reverse the condition and branch to the other target
                        <--- eliminate/omit the unconditional branch and other label
    ble a0,t0,skip_add
    mv a0, t0
skip_add:
20.05.2020
Новые материалы
Кластеризация: более глубокий взгляд
Кластеризация — это метод обучения без учителя, в котором мы пытаемся найти группы в наборе данных на основе некоторых известных или неизвестных свойств, которые могут существовать. Независимо от..
Как написать эффективное резюме
Предложения по дизайну и макету, чтобы представить себя профессионально Вам не позвонили на собеседование после того, как вы несколько раз подали заявку на работу своей мечты? У вас может..
Частный метод Python: улучшение инкапсуляции и безопасности
Введение Python — универсальный и мощный язык программирования, известный своей простотой и удобством использования. Одной из ключевых особенностей, отличающих Python от других языков, является..
Как я автоматизирую тестирование с помощью Jest
Шутка для победы, когда дело касается автоматизации тестирования Одной очень важной частью разработки программного обеспечения является автоматизация тестирования, поскольку она создает..
Работа с векторными символическими архитектурами, часть 4 (искусственный интеллект)
Hyperseed: неконтролируемое обучение с векторными символическими архитектурами (arXiv) Автор: Евгений Осипов , Сачин Кахавала , Диланта Хапутантри , Тимал Кемпития , Дасвин Де Сильва ,..
Понимание расстояния Вассерштейна: мощная метрика в машинном обучении
В обширной области машинного обучения часто возникает необходимость сравнивать и измерять различия между распределениями вероятностей. Традиционные метрики расстояния, такие как евклидово..
Обеспечение масштабируемости LLM: облачный анализ с помощью AWS Fargate и Copilot
В динамичной области искусственного интеллекта все большее распространение получают модели больших языков (LLM). Они жизненно важны для различных приложений, таких как интеллектуальные..