含光800NPU开发指南(二)【芯片与软件栈系列之----含光十八式】

简介: 前言 本章节介绍基于HanGuangAI软件运行时(RunTime)的开发。这些运行时编程接口既可以整合到框架中,也可以用来实现推理引擎,或者直接被AI应用程序使用。现阶段,他们是运行时控制使用含光NPU的唯一编程接口。 当前AI计算芯片的架构各异,表现在软件接口上,就是没有一套标准的编程接口。Nvidia的领头羊地位,由其通用计算拓展到AI计算领域,但由于芯片架构之间差别太大,它的编程接口并

前言

本章节介绍基于HanGuangAI软件运行时(RunTime)的开发。这些运行时编程接口既可以整合到框架中,也可以用来实现推理引擎,或者直接被AI应用程序使用。现阶段,他们是运行时控制使用含光NPU的唯一编程接口。

当前AI计算芯片的架构各异,表现在软件接口上,就是没有一套标准的编程接口。Nvidia的领头羊地位,由其通用计算拓展到AI计算领域,但由于芯片架构之间差别太大,它的编程接口并不适合其他架构。况且就是Nvidia自己,也有不同层次,不同目的的编程接口:从底层的CUDA驱动接口,到CUDA运行库,TensorRT,以及其他的运算库。

我们在设计自己的编程接口的时候,尽量使用一些被普遍使用的名词和组织方式,以方便开发者能快速了解和掌握含光NPU的编程。因此,如果你熟悉CUDA/TensorRT,会有一些熟悉的感觉。但是,由于NPU硬件架构,编程模型的一些独特之处,HanGuangRT编程接口也有很多的自己的特性,需要开发者特别地关注和学习。

此部分作为“含光十八式”的第二式,像是经过第一式的剑舞而蓄满力量,然后发出迅猛而凌厉的一剑。不见剑,只见一道光闪出,划过天空------“鹰击”。

注:当你准备阅读此文时,如果你没有阅读过《含光800NPU编程模型》,请你一定要先仔细地读一读编程模型。它能帮助你更好地理解下面的开发指南和例程。同时,本文将是一个指引,更具体的文档在《HanGuangAI SDK》。如想了解更细节的信息,请阅读开发文档。

概要

特性

HanGuangRT编程接口和其他的深度学习编程接口看起来有很多相同点,但也有自己的一些特点:

  • 统一的编程接口

HanGuangAI的编程接口,既包括设备的控制,也包括运行时的上下文,执行管理,以及资源管理等,是当前调用设备的唯一编程接口。驱动程序作为底层的接口,没有直接暴露给用户调用。

  • C语言接口

使用C语言作为接口编程语言,简单易用,移植性好,高性能。其中一些接口,主要是查询功能的接口,会经过包装生成Python接口提供。

  • 运行前编译(AOT)

提前使用Python接口(后续根据需要增加C接口)编译链接好,生成执行计划和硬件代码,并做序列化。推理运行时反序列化然后执行。

后期会考虑需要提供运行时编译JIT (Just in Time) 的方式,因为有一些使用场景JIT是有一些优势的。

    • 不需要序列化和反序列化,
    • 灵活地根据运行时物理设备和核心的实际可使用情况来编译。不用提前准备多份配置的编译结果。
    • 能更方便的提高NPU的利用率

当然,运行时编译产生的延迟是需要考虑的。

  • 显式和隐式相结合的核心分派

HanGuangRT以核心为单位做资源调度,提供灵活的设备核心使用方式。

  • 以执行计划作为整体来分配资源

把一个业务场景作为一个整体,为保证完整的场景能流畅运行,创建一个相关引擎组的执行计划,以执行计划作为整体来分配资源。

常用名词

为方便用户阅读和理解,特对一些常用语进行统一简单的解释,后面具体章节还会对一些用语做详细地介绍:

  • 设备(Device/NPU):此处指的是含光800NPU(Neural-network Processing Unit),一个设备就是一块NPU卡,通常包括多个NPU运算核心。多个设备之间没有之间连接。同一个系统上的多个设备是通过PCIE传输数据。
  • 核心(Core):NPU的一个完整的计算核心,可独立调度运行的最小单位,核心之间通过On-Chip Bus连接。
  • 本地存储(Local Memory/LM):每个核心有独立的片上存储(LM)。LM只能被自己的核心访问。核间通过总线CHUB可以连接。
  • 模型(Model):特指深度神经网路模型。不同的框架有可能有不同的模型文件格式。有的框架,如Mxnet,会有不止一个文件一起表示一个模型。
  • 算子(Operator):是构建神经网络的基本单位和必要元素,定义了输入到输出的映射关系。
  • 子模型(Model Segment):简称segment,对一个完整的网络模型进行分割,得到的包含部分算子的子网络。
  • 引擎(Engine):一个模型或者子模型,经过NPU软件栈编译之后,得到的一个用于只能在NPU上执行的单元。对框架来说,这也是一个自定义算子,称为含光NPU引擎算子(HanGuang Engine Op)。
  • 引擎组(Engine Group):基于含光800NPU的特性,通常多个引擎需要共享一个设备或者部分核心。因此多个引擎需要作为一个整体来进行编译链接。这些引擎称为一个引擎组。
  • 引擎控制(Engine Control):用于描述一个引擎执行的控制参数,包括核心的分配方式,单个batch需要的核心数量,本地存储的消耗,以及用来标明引擎的ID和名。
  • 执行规划(Execution Scheme):执行规划是一个引擎组的所有引擎在一个核或者多核上的执行控制。是一个引擎控制列表。每个引擎里都带有整个引擎组的执行规划以方便查询。
  • 执行上下文(Execution Context):执行上下文是由一个引擎对象创建出来的特殊的上下文,是推理运行的核心数据和状态。 此上下文只能用于执行该引擎。每个引擎对象现在只支持一个执行上下文。
  • 张量(Tensor):用做NPU引擎的输入和输出的存储对象。张量的存储可以设置创建于不同的存储中。

HanGuangRT C语言编程接口

总的说来,含光800NPU的推理执行主要包含以下几个方面的接口:

  • Version Query: 软件版本信息。
  • Error Query: 查询错误的详细信息。
  • Device Management: 设备-device,核心-core的配置管理以及状态查询等。
  • Engine Management: 创建HanGuangAI引擎,查询输入输出绑定,执行计划等信息,为推理执行做准备。
  • Execution Scheme: 获取引擎所在组的执行计划,得到本引擎的控制信息。
  • Execution Context: 根据查询的绑定和准备好的输入输出数据和缓存,选定核心分配的策略,执行推理运行。
  • Tensor Management: 张量对象用于管理输入和输出的张量,包括创建,查询,数据的上传和下载等操作。

image.png

如上图所示,HanGuangRT提供了两种不同的方式来让开发者使用NPU做推理运行。

  • 一种方式HanGuangRT负责隐式的核心分派。这是对一般的使用场景,比如单模型单设备,开发者不需要知道负责的调度接口,直接使用引擎,绑定,选用合适的核心分配策略,由Runtime来负责分配和映射的工作。这样,开发者不用了解太多的设备,执行计划等细节,只需要使用图上左边的部分接口就可以了。
  • 另一种方式,是开发者使用API自己控制核心分派。这是对比较复杂的使用场景,开发者有更多的需求,对含光NPU的软硬件比较了解的情况下,比较适合的一种开发方式。这时候,开发者需要使用大部分HanGuangRT的接口。下面具体地讲解一些细节。

版本和错误信息查询

版本查询(Version Query)用于查询API的版本,保证不同版本之间的应用程序兼容性。
错误查询(Error Query)用于解析其他API返回的RTLresult结果,用于得到错误的名称和描述。

设备管理

设备管理API用于查询设备的信息,包括设备的数量,每个设备上核心的数量,本地存储的大小等;还可以显式地获取和管理设备和核心。和GPU或者其他的AI芯片不大一样的是,含光800NPU的设备管理是以核心为基本单位的。表现在编程接口上,就是需要指定设备的索引和核心的Mask。

设备切换

多个设备时,设备索引从0开始编号。通过hgDeviceSetCurrent可以设置当前的设备,后面的其他操作都是基于当前的设备上的,包括创建的引擎,执行上下文,张量等都属于当前的设备,不能在其他的设备上使用。

设备占用

从编程模型一章节我们了解到,含光800NPU是将模型参数常驻本地存储的高效方式工作。模型的上传是一个比较费时的动作,上传之后希望保持模型对核心的占有状态。因此,开发者需要了解和管理设备核心被模型引擎的占有状态。

我们提供了两种设备核心的占有方式,一种是显式地使用设备管理API占有和释放。一种是隐式地由引擎的执行上下文来占有和释放。显式占有设备的API:

hgResult hgDeviceRetain(hgDevice device, unsigned int coreCount, 
                        hgDevicePriority priority, 
                        unsigned int* retainedCoreMask);
hgResult hgDeviceRelease(hgDevice device, unsigned int coreMask);

设备核心共享

为提高设备核心利用率,有时需要多个模型/引擎共享核心。之前的章节中讲述了编译的时候如何让多个模型共享核心,这是一种静态的共享方式。运行的时候,这几个模型会装载到相关对应的物理核心上,然后在这些模型引擎释放之前,其他的模型将不能再往这些核心上上传。

动态核心共享,就是在运行时查看能不能将一个引擎放在一个或多个已被占用的核心上。这种业务需求现在来看还很少,暂时不被支持。

引擎管理

引擎管理的功能包括将编译后序列化的二进制数据反序列化生成引擎对象,查询引擎的相关信息,包括输入输出绑定和这个引擎所在的执行计划等,并根据相关信息来创建该引擎的执行上下文对象。输入输出绑定信息在执行引擎的时候需要做对应的配置。

深度理解引擎

如何深刻地理解HanGuangAI中的引擎的概念呢?

  • 从原始网络模型的角度看,引擎所代表的是一个网络模型和或者是其中的一段子网络模型,这段网络模型是被HanGuangAI编译器分割出来的,计划被HanGuangAI执行的部分。
  • 从编译后网络模型的角度看,引擎是其中的一个节点,一个特别的被HanGuangAI支持的算子。
  • 从数据内容的角度看,引擎里面包含了多种信息的数据,这些数据在编译的时候生成,在执行的时候需要使用。主要数据有:
    • NPU硬件指令;
    • 模型参数,包括权重,常量等;
    • 绑定(输入,输出,常量等)的描述,属性信息;
    • 执行计划,引擎执行所需的一些参数。
  • 从生命周期的角度看,
    • 编译后的引擎以序列化的二进制形式存在。
    • 运行时的引擎对象创建(hgEngineCreate)之后,反序列在系统内存中。
    • 引擎的执行上下文创建(hgEngineCreateExecutionContext)成功后,引擎里的指令,模型参数装载进NPU

引擎绑定

引擎的绑定(Bindings)指的是引擎运行的时输入输出张量的抽象,也就是引擎所表示的这个子网络的输入和输出。针对引擎,提供了一系列的接口来获取引擎的绑定信息,这些信息是准备输入数据,准备输入输出张量的存储等的必要信息。具体的包括:

  • 绑定的个数,索引,名词,数据维度
  • 是否是输入,布局等信息。

这些信息由一系列的接口hgEngineGetBindingXxx()来提供。

其他

后面会用到的其他一些与引擎相关的接口包括:

  • hgEngineGetExecutionScheme:获取引擎所在的引擎组执行计划。
  • hgEngineGetEngineID:获取引擎所在的引擎组执行计划里的ID。此ID可用于查询引擎控制信息。
  • hgEngineGetMaxBatchSize:获取引擎所允许的最大批处理大小。可设置flags用于指定计算批处理大小的一些信息:张量是否是在Host memory;引擎的执行上下文是不是以最大核心数来分配的。参见hgBatchSizeFlags的定义。

执行上下文

执行上下文是由一个引擎对象创建出来的特殊的上下文,是推理运行的核心数据和状态。 此上下文只能用于执行创建它的引擎。同时,每个引擎对象现在只支持一个执行上下文。

执行上下文有两个重要的接口,一个是创建,一个是执行。

创建

创建一个执行上下文,主要是需要给引擎的执行分配核心和上传引擎的模型参数。这是一个比较重要的步骤。如果创建失败,则说明分配不成功,需要重新考虑如何分配资源,或者等待资源释放以后再使用。根据优先级做逐出(eviction)的机制还没有实现。

核心分配也是有显式的和隐式的两种,可以由hgCoreAllocPolicy来指定。这两种方式有很大的区别:

  • 隐式的,是根据整个执行组(scheme)所需要的核心为基本单位,使用HG_CORE_ALLOC_MINIMUM或者HG_CORE_ALLOC_MAXIMUM。前者是只分配一个执行组所需的核心,后者是尽可能的多分配核心,也就是1~N倍一个执行组所需的核心。
  • 显式的,是由开发者直接指定当前单个引擎所需要的核心,开发者必须通过下一节的执行控制来获取相关信息,同时获得设备信息,然后手动给个引擎分配好核心,必须保证分配正确,否则会发生分不成功的问题。这一模式对开发者要求比较高。需要深刻地了解相关的信息和设置方式。

创建执行上下文的接口是:

hgResult hgEngineCreateExecutionContext(hgEngine engine, hgExecutionContext* context,     
                                        hgCoreAllocPolicy policy, uint32_t coreMask);

执行

同步执行

当前,HanGuangAI运行时只提供了一种同步执行的机制。也就是执行函数调用会等待执行完成,得到输出之后才会返回。异步的enqueue机制还没有加入到执行接口中。

由于没有异步的执行方式,所以为了达到更高的吞吐,开发者可以一次送入大批量的数据,批量大小以batchSize设置。最大的batchSize可以由接口hgEngineGetMaxBatchSize查询得到。

执行之前,还需要把输入和输出的数据绑定设置好。绑定可以是数据的系统存储(System Memory)的地址,也可以是创建在Locked Host Memory的张量对象句柄。后面在张量对象里面介绍两种区别。hgHostTensorDesc用于配置一些Host张量的信息,用以帮助解析这些张量的数据。

接口定义为:

hgResult hgExecutionContextExecute(hgExecutionContext context, int batchSize, 
                                   void** bindings, const hgHostTensorDesc* tensorInfo);

多批量执行

含光800NPU计算核心算力强劲,在多数情况下,使用更大的批量输入,能够更高效的利用计算核心,提高整个NPU的计算吞吐。

特别的,HanGuangRT对多批量的执行进行了优化,在上传,运算,下载三个步骤之间做多线程异步处理,形成了更好的流处理工作模式。因此在多数追求吞吐量的使用场景里,应该使用更大数目的“batchSize”批量执行。

执行计划

执行计划(Execution Scheme)是HanGuangAI所提供的一个特别的概念。它是为多引擎装载而生。具体地说,它是为了静态地给多个引擎分配核心和装载模型参数,从而保证整个业务流程能顺利地在指定的设备核心上运行。所以当一个引擎运行的时候,会将同一个scheme里的其他引擎所需的核心也一起分配好。但不论基于框架还是独立的推理引擎,引擎都是一个一个独立运行的,为了能一起分配资源,需要每个引擎里必须有整个执行组的所有信息。

前面提到,对执行组所需要的资源,我们提供了两种获取方式,一种是显式的,一种是隐式的。这里,如果需要显式地

编程接口

从一个引擎里获得它所属的执行引擎的接口是:

hgResult hgEngineGetExecutionScheme(hgEngine engine, hgExecutionScheme* scheme);

然后,可以查看执行组里一共有多少个引擎:

hgResult hgSchemeGetEngineCount(hgExecutionScheme scheme, int* count);

其中,每个引擎的ID可以由下面的接口从引擎中获得:

hgResult hgEngineGetEngineID(hgEngine engine, int* engineId);

最后,可以从执行计划里读取每个引擎的执行控制(Engine Control):

hgResult hgSchemeGetEngineControl(hgExecutionScheme scheme, int engineId, 
                                  hgEngineControl** engControl);

数据结构

每个引擎的执行信息,定义为hgEngineControl,它包括的信息如下:

typedef struct hgEngineControl
{
    /// engine index in the engine group
    int                 engineId;
    /// name string of the engine
    std::string         engineName;
    /// virtual device to put the engine on,
    /// engines with same virtual device id share the same device
    int                 virtualDeviceId;
    /// engines with same group ID can share memory
    int                 engineGroupId;
    /// execution mode :normal, weight_split,
    /// engines with same virtual device id should have same execute mode
    hgExecuteMode       executeMode;
    /// the minimum core number for execution of one batch
    int                 coresPerBatch;
    /// the virtual core mask on the virtual device
    int                 coreMask;
    /// local memory consumption of the engine for one patch
    size_t              memoryConsumption;
}hgEngineControl;

虚拟设备核心

在执行计划和引擎控制中,使用的设备ID,核心Mask,都是以编译的时候提供的设备数和核心数作为虚拟设备和核心做的编号。设备ID从0开始做索引,核心Mask也是从bit0开始做索引。

在隐式分配设备核心的时候,HanGuangRT会内部生成引擎的Scheme对象,根据相关的信息做核心分配以及虚拟核心和物理核心之间的映射(mapping)。如果开发者想要显式地分配,可以通过相关的API查询物理核心和执行计划信息,做好映射关系,然后通过对应的API来设置。

张量管理

张量(Tensor),用做NPU引擎的输入,输出的存储对象。张量对象的操作包括根据描述创建对象,查询描述和大小属性,map/unmap可用于用户自己上传和下载数据。也可以使用接口交由运行时来上传/下载数据。

输入数据的上传和输出数据的下载有两种方式:

  1. 将数据放在System Memory,将地址作为binding指针传入,同时使用System Memory指针作为接收输出的binding。这种方式下,Runtime会负责数据在System Memory和NPU Host Memory之间的传输。在这种工作方式中,上层应用不需要使用张量接口也可以执行推理。接口上比较简单方便。
  2. 使用张量接口,创建Host Memory的张量对象,上层应用将数据直接拷贝到Map出来的空间里。当然拷贝的时候需要主要数据的对齐。对齐后的大小可以查询获得。在有些情况下,后面这种方式可以减少一次拷贝,对性能和带宽有帮助。

Tensor由下面API创建。

 typedef enum hgMemFlags
 {
     HG_MEM_SYSTEM    = 1 << 0,  // CPU memory
     HG_MEM_HOST      = 1 << 1,  // page locked host memory
 }hgMemFlags;
 
 hgResult hgTensorCreate(const hgTensorDesc* tensorDesc, 
                         const hgMemDesc * memDesc, 
                         unsigned int flags, 
                         hgTensor *handle);

其它几个比较重要的API:

/// If the tensor hasn't be created with desc, this call will set and allocate mthe underlying
/// meemory for the tensor. If the tensor has already be set with desc, the call will update 
/// the desc and create the tensor memory if necessary 
hgResult hgTensorUpdateDesc(hgTensor handle, const hgTensorDesc* desc);

/// Uploads the \p data into the tensor object
hgResult hgTensorData(hgTensor handle, const void *data, size_t size);

/// Map the tensor to get CPU access address 
hgResult hgTensorMap(hgTensor handle, void **data);

/// Unmap the tensor to complete access
hgResult hgTensorUnmap(hgTensor handle);

更多的Tensor使用请参考文档。 

HanGuangRT简单例程

本例程主要介绍怎么使用HanGuangRT提供的API在NPU上做推理。在做推理之前,用户需要准备好:

  1. 使用HanGuangAI量化编译得到的序列化的EngineOp
  2. 此EngineOp对应的输入输出的数据和相关信息

头文件

#include "alinpu_hgrt_c_api_pub.h"

查询NPU设备信息

首先,查询runtime的版本,需要和之前编译EngineOp使用的HanGuangAI是同一个版本。可以根据发布的对应版本的文档知道相应的功能,API的情况,避免版本不对导致错误的使用

int runtimeVersion;
hgRuntimeGetVersion(&runtimeVersion);

可以查询当前系统里Device的情况,包括有几个NPU,每个NPU的核心的数目,和相应的LM的大小。显式指派核心的时候需要相关信息。

int count = 0;
hgDeviceGetCount(&count);
CHECK(count > 0);
hgDevice original;
hgDeviceGetCurrent(&original);
int cores;
hgDeviceGetAttribute(original, HG_DEVICE_CORE_COUNT, &cores);
...

显式获取设备核心

下面的API可以显式地获取和释放设备核心,如果没有复杂的使用场景,推荐用户使用隐式的机制,应用程序不用显式地获取设备核心。

uint retainedCoreMask = 0;
int cores = 2;
hgDeviceRetain(device, cores, HG_DEVICE_P0, &retainedCoreMask);
...
if (retainedCoreMask > 0) {
  hgDeviceRelease(device, retainedCoreMask);
}

创建引擎

使用编译后序列化的引擎数据创建引擎。独立运行时,不用指定框架。

hgEngineCreate(serialized_engine_.c_str(), 
               serialized_engine_.size(),
               &alinpu_engine_ptr_);

查询执行计划信息

从引擎里查询单个执行计划里的引擎的信息,以帮助选定设备的核心。

 int engine_id = 0;
 hgEngineGetEngineID(alinpu_engine_ptr_, &engine_id);
 hgExecutionScheme scheme;
 hgEngineGetExecutionScheme(alinpu_engine_ptr_, &scheme);
 int engine_count = 0;
 hgSchemeGetEngineCount(scheme, &engine_count);
 for (int i = 0; i < engine_count; i++) {
     hgEngineControl* control;
     hgSchemeGetEngineControl(scheme, i, &control);
}

hgEngineControl的详细信息见API参考手册。当一个执行计划里有多个引擎的时候,执行计划里包含了引擎和设备核心的对应关系。查询执行计划信息是执行推理的必要步骤。

创建执行上下文

根据查询得到的执行计划信息,创建执行计划上下文。

// try create alinpu context.
hgEngineCreateExecutionContext(alinpu_engine_ptr_,
                               &alinpu_execution_context_ptr_,
                               HG_CORE_ALLOC_MINIMUM, 0);
// if create context fail, exit the function.
if (alinpu_execution_context_ptr_ == nullptr) {
  LOG(ERROR) << "Create Execution Context failed!\n";
  return false;
}

配合获取设备核心的两种方式,创建执行上下文的时候,也有两类对应的策略hgCoreAllocPolicy:

  • 隐式的策略,包括HG_CORE_ALLOC_MINIMUM, HG_CORE_ALLOC_MAXIMUM,前者提供最小的分配,一次一个批次(batch)。而后者是高性能模型,将为此执行计划里的引擎分配尽可能多的核心,以保证最高的性能和吞吐。
  • 如果核心是显式的获取,可以使用HG_CORE_ALLOC_AS_CORE_MASK来指定合适的物理核心给此引擎。

准备引擎输入输出

首先查询所有输入和输出绑定的属性。

// input/output bindings
int32_t num_binding_;  
hgEngineGetNbBindings(alinpu_engine_ptr_, &num_binding_);
buffers_.resize(num_binding_);
for (int i = 0; i < num_binding_; i++) {
  hgEngineGetBindingAttribute(alinpu_engine_ptr_, i, 
                              HG_BINDING_ATTR_IS_INPUT, 
                              &is_input_[i]);
  ...
}

根据上面的信息,设置和分配输入输出的buffer。

同步执行,得到输出数据

最后,使用上面得到的批量大小num_batch,绑定缓存buffers_,和Host张量的信息hinfo_执行引擎。

// execute alinpu engine op.
hgResult ret = hgExecutionContextExecute(alinpu_execution_context_ptr_, 
                                         num_batch, &buffers[0], &hdesc);

后记

HanGuangRT还处于继续开发当中,一方面,新的功能接口会陆续地加进来,另一方面,原有的接口可能也会有一些改动,请关注我们最新的文档,它会随着软件栈的发布一起更新。你有任何疑议或建议,请联系我或者请发送邮件到:ratelnn@alibaba-inc.com

相关文章
|
3天前
|
C++
【洛谷 P1044】[NOIP2003 普及组] 栈 题解(递归+记忆化搜索)
**NOIP2003普及组栈问题**:给定操作数序列1到n,仅允许push(进栈)和pop(出栈)操作。目标是计算所有可能的输出序列总数。输入包含一个整数n(1≤n≤18)。示例输入3,输出5。当队列空时返回1,栈空则只能入栈,栈非空时可入栈或出栈。AC C++代码利用记忆化搜索求解。
6 1
|
5天前
|
算法
$停车场管理系统 栈与队列
$停车场管理系统 栈与队列
6 1
|
9天前
数据结构 栈 / 队列(第9天)
数据结构 栈 / 队列(第9天)
|
2天前
|
缓存 调度
栈和队列的区别
栈和队列的区别
5 0
|
3天前
|
存储 程序员 编译器
堆和栈的区别
堆和栈的区别
|
3天前
|
C++
【洛谷 P1739】表达式括号匹配 题解(栈)
该编程题目要求检查给定的包含字母、运算符和括号的表达式是否括号匹配。输入为一行表达式,以`@`结束。如果括号匹配,输出`YES`,否则输出`NO`。样例包括一个匹配和一个不匹配的表达式。解决方案是使用栈,遇到左括号入栈,遇到右括号时判断栈是否为空,栈空则输出`NO`,否则出栈。当读到`@`时,栈空则输出`YES`,否则输出`NO`。提供的AC代码使用C++实现,通过`stack`处理括号匹配。
5 0
|
3天前
|
存储 Java Python
数据结构===栈
数据结构===栈
|
4天前
|
索引
栈的数组实现
栈的数组实现
5 0
|
6天前
|
存储 缓存 算法